数据结构与算法精解：顺序栈
顺序栈是一种基于数组实现的栈结构，具有后进先出(LIFO)特性。本文介绍了顺序栈的基本概念、操作方法和应用场景。顺序栈支持push、pop、peek等基本操作，并能动态扩展存储空间，常用于函数调用、表达式求值等场景。文章详细阐述了顺序栈的C语言实现，包括头文件引入、结点设计、接口函数定义及具体实现。实现部分涵盖了静态和动态两种顺序表的初始化、数据插入删除、查找等核心功能，展示了顺序栈从理论到代码的完整实现过程。
什么是顺序栈？
顺序栈（Sequential Stack）是一种使用数组来实现的栈数据结构。栈是一种后进先出（Last In First Out, LIFO）的数据结构，只允许在栈顶进行数据的添加（push）和删除（pop）操作。一下是顺序栈的特点：
1.使用数组实现：顺序栈通常使用一个固定大小或动态大小的数组来存储栈中的元素
2.动态扩展：在栈满时，如果使用动态数组，可以自动扩展数组的大小以容纳更多元素
3.LIFO特性：元素只能从栈顶添加或移除，这保证了最后添加的元素将是第一个被移除的
顺序栈的基本操作和应用
要实现顺序栈，则先需要了解顺序栈的基本操作：
1.Push：向栈顶添加一个元素。如果栈已满，这可能会触发数组的扩展（如果使用动态数组）
2.Pop：移除栈顶的元素，并返回它。如果栈为空，Pop操作可能会失败或抛出异常
3.Peek/Top：查看栈顶元素但不移除它
4.IsEmpty：检查栈是否为空
5.GetSize：获取栈中元素的数量
以下是顺序栈的应用：
1.函数调用：在编程中，顺序栈常用于跟踪函数调用的返回地址
2.表达式求值：用于评估和简化算术表达式，如逆波兰表示法的计算
3.括号匹配：检查代码或文本中的括号是否正确匹配
4.回溯算法：在需要回溯到之前状态的算法中，如迷宫求解或游戏AI
包含头文件
#include<stdio.h>#include<stdlib.h>结点设计
#define Initsize 10typedef int Elemtype;typedef struct { Elemtype data[Initsize]; //定义数组data大小为Initsize，存储的是静态顺序表的数据 Elemtype* next; //定义next为Elemtype类型的指针，用于动态扩展顺序表的大小 int Maxsize; //定义变量Maxsize存储顺序表的大小 int lenth; //定义变量lenth存储顺序表所存储的数据个数}SqlList;接口函数定义
void PrintfList(SqlList& A); //用于输出顺序表void InputList(SqlList& A); //用于输入顺序表中的数据void InitStaticList(SqlList& A); //用于初始化静态顺序表void InitMoveList(SqlList& A); //用于初始化动态顺序表void AddList(SqlList& A); //用于动态增加顺序表长度bool ListInsert(SqlList& A, int len, int X); //用于在顺序表中插入数据bool ListDelete(SqlList& A, int len, int &X); //用于在顺序表中删除数据Elemtype GetElem(SqlList& A, int len); //用于在顺序表中按位查找数据Elemtype LocateElem(SqlList& A, int X); //用于在顺序表中按值查找数据接口函数实现
Elemtype LocateElem(SqlList& A, int X) { //用于在顺序表中按值查找数据 int i; if (A.next == NULL) { //判断传入的是否为静态顺序表 for (i = 0; i < A.lenth; i++) { if (A.data[i] == X) { //遍历静态顺序表，查询是否有数据相同 printf("该数据位于的顺序表中的次序为%d", i + 1); return i + 1; } } printf("在该顺序表中未能找到此数据"); return 0; } else { for (i = 0; i < A.lenth; i++) { if (A.next[i] == X) { //遍历动态顺序表，查询是否有数据相同 printf("该数据位于的顺序表中的次序为%d", i + 1); return i + 1; } } printf("在该顺序表中未能找到此数据"); return 0; }}Elemtype GetElem(SqlList& A, int len) { //用于在顺序表中按位查找数据 if (len<1 || len>A.lenth) { //判断传入的次序是否合理 printf("输入的次序有误"); return 0; } if(A.next==NULL) { //判断传入的是否为静态顺序表 printf("您查找的数据为%d", A.data[len - 1]); return A.data[len-1]; } else { printf("您查找的数据为%d", A.next[len - 1]); return A.next[len-1]; }}bool ListDelete(SqlList& A, int len, int &X) { //用于在顺序表中删除数据 int i; if (len<1 || len>A.lenth) { //判断传入的次序是否合理 printf("输入的次序有误"); return false; } if (A.next == NULL) { //判断传入的是否为静态顺序表 X = A.data[len - 1]; //将要删除的数据带回 printf("删除的数据为%d", X); for (i = len - 1; i < A.lenth; i++) { A.data[i] = A.data[i + 1]; //将静态顺序表中的数据依次前移 } A.lenth -= 1; //更新静态顺序表中的数据 return true; } else { X = A.next[len - 1]; //将要删除的数据带回 printf("删除的数据为%d", X); for (i = len - 1; i < A.lenth; i++) { A.next[i] = A.next[i + 1]; //将动态顺序表中的数据依次前移 } A.lenth -= 1; //更新动态顺序表中的数据 return true; }}bool ListInsert(SqlList& A, int len, int X) { //用于在顺序表中插入数据 int i; if (A.lenth >= A.Maxsize) { //判断传入顺序表中含有的数据是否以满 printf("该顺序表填充数据已满"); return false; } if (len<1 || len>A.lenth + 1) { //判断传入的次序是否合理 printf("输入的次序有误"); return false; } if (A.next == NULL) { //判断传入的是否为静态顺序表 for (i = A.lenth; i >= len; i--) { A.data[i] = A.data[i-1]; //将次序后的数据依次后移 } A.data[len - 1] = X; //更新静态顺序表中的数据 A.lenth += 1; return true; } else { for (i = A.lenth; i >= len; i--) { A.next[i + 1] = A.next[i]; //将次序后的数据依次后移 } A.next[len - 1] = X; //更新动态顺序表中的数据 A.lenth += 1; return true; }}void AddList(SqlList& A) { //用于动态增加顺序表长度 int i,len; printf("当前顺序表的大小为%d，请问要在原基础上增加多少存储空间?"); scanf_s("%d", &len); Elemtype* Q = (Elemtype*)malloc(sizeof(Elemtype) * (A.Maxsize + len)); if (A.next == NULL) { //判断该顺序表是否为静态初始化的顺序表 for (i = 0; i < A.lenth; i++) { //将静态顺序表中的数据更新到新的地址上 Q[i] = A.data[i]; } } A.next = Q; //更新顺序表中的数据 A.Maxsize += len;}void InputList(SqlList& A) { //用于输入顺序表中的数据 int i,X; if (A.next == NULL) { //判断传入的顺序表是否为静态顺序表 printf("输入静态顺序表要存储的数据个数(最大为10):"); scanf_s("%d", &X); for (i = 0; i < X; i++) { scanf_s("%d", &A.data[i]); //循环输入数值，赋值于静态顺序表中的数组里 } A.lenth = X; } else { printf("您所创建的动态顺序表大小为%d，请问您要输入的数据个数:", A.Maxsize); scanf_s("%d", &X); for (i = 0; i < X; i++) { scanf_s("%d", &A.next[i]); //循环输入数值，赋值于动态顺序表中的地址里 } A.lenth = X; }}void PrintfList(SqlList& A) { //用于输出顺序表 int i; if (A.next==NULL){ //判断传入的顺序表是否为静态顺序表 for (i = 0; i < A.lenth; i++) { printf("%d ", A.data[i]); //循环输出静态顺序表中的数据 } } else { for (i = 0; i < A.lenth; i++) { printf("%d ", A.next[i]); //循环输出动态顺序表中的数据 } }}void InitMoveList(SqlList& A) { //用于初始化动态顺序表 int len,i; //定义变量len用于存储动态创建的顺序表大小 printf("请问想要向计算机申请多大的顺序表?"); scanf_s("%d", &len); A.next= (Elemtype *)malloc(sizeof(Elemtype) * len); for (i = 0; i < len; i++) { A.next[i] = 0; } A.Maxsize = len; //调用动态顺序表中的Maxsize存储动态顺序表大小 A.lenth = 0; //调用动态顺序表中的lenth存储动态顺序表中数据的个数，默认为0 printf("初始化动态单链表成功");}void InitStaticList(SqlList& A) { //用于初始化静态顺序表 int i; for (i = 0; i < Initsize; i++) { //将传入的静态顺序表的初始值全部赋值为0 A.data[i] = 0; //调用静态顺序表中的data数组并依次赋值 } A.Maxsize = Initsize; //调用静态顺序表中的Maxsize存储静态顺序表大小 A.lenth = 0; //调用静态顺序表中的lenth存储静态顺序表中数据的个数，默认为0 A.next = NULL; printf("初始化静态单链表成功");}3次原文点赞；这里的喜欢仅保存在本机