一、顺序栈的基本概念
栈是限定仅在表尾进行插入或删除的线性表，又称为先进后出的线性表，本质是操作受限的线性表。
因此对于栈来说，表尾端有特殊的含义，称为栈顶，表头端称为栈顶。
顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。
二、顺序栈要实现的基本功能及应用
实现工具：Dev
顺序栈要实现的基本功能：
- 构造一个空的顺序栈
- 批量元素入栈
- 对顺序栈进行销毁
- 对顺序栈进行重置
- 判断顺序栈是否为空
- 获取顺序栈的长度
- 获取栈顶元素
- 插入新的栈顶元素并返回其值
- 删除当前栈顶元素并返回其值
- 打印顺序栈
顺序栈要实现的简单应用：
- 括号匹配的检验
- 数制转换
二、代码实现：
1. 准备工作
在dev新建一个Source File文件即可
File>new>Source File
在实现程序时导入的头文件有
在这里我调用windows头文件是为了在后面的代码中修改控制台的名称，在实现线性表的顺序结构时真正用到的只有前三个头文件在写代码之前先对一些表示结果状态的字符进行预定义
//函数结果状态代码 //代码中出现TRUE相当于出现了1 //出现FALSE相当于出现了0 //出现OK相当于出现了1 //出现ERROR相当于出现了2typedefintStatus; typedefintSElemType;
在这里使用了typedef定义了Status和SElemType为int类型，也就是说之后的代码当中如果出现了Status和ElemType，它们与int作用相同
2. 顺序栈动态分配顺序存储结构
代码如下：
//栈的储空间的初始分配量 //栈的存储空间的分配增量typedefstruct{ SElemType*top; //栈顶指针 SElemType*base; //栈底指针，在构造栈时和销毁栈时均为NULL intstacksize; //当前已经分配的存储空间 }SqStack;
3.构造一个空的顺序栈
代码如下：
//构造一个空的顺序栈 StatusInitStack(SqStack&S) { S.base= (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); //开辟一块连续的空间 if(!S.base) //如果存储空间分配失败 exit(OVERFLOW); S.top=S.base; //当栈为空栈时栈底和栈顶指针位置相同S.stacksize=STACK_INIT_SIZE; //更新栈的空间大小returnOK; }
在构造空线性表时参数加&符号表示引用传递，确保形参和实参同时改变
S.base为顺序栈的栈底指针，S.top为顺序栈的栈顶指针，S.stacksize为顺序栈当前分配的空间大小
图示：
在这里解释一下为什么顺序表中有L.length来表示当前表中的元素个数而顺序栈中没有S.length来表示当前顺序栈中的元素个数？
原因： 因为在顺序栈中，有S.base栈底指针一直指向栈底，而S.top栈顶指针一直指向这栈顶元素的下一个位置，所以当前栈中的元素个数就是S.top-S.base，因此不需要再单独定义length来表示栈中的元素个数。
4. 批量元素入栈
代码如下：
//批量元素入栈StatusValueStack(SqStack&S,intNum) { if(!S.base){ //如果栈不存在 printf("栈不存在，元素无法入栈\n"); returnERROR; } if(S.base!=S.top){ //判断传来的顺序栈中是否为空栈if(Num>=S.stacksize){ //如果要入栈的元素数量大于栈的空间大小 S.base= (SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT) *sizeof(SElemType)); S.stacksize=S.stacksize+STACKINCREMENT; //更新栈的空间大小 } inttemp[Num]; //定义一个辅助数组 for(inti=1;i<=Num;i++){ printf("请输入第%d个元素的值：",i); scanf("%d",&temp[i-1]); //将之后输入的值暂时存储在临时数组中 } for(intj=1;j<=Num;j++){ *S.top=temp[j-1]; S.top++; } printf("%d个元素入栈成功\n",Num); } else{ for(inti=1;i<=Num;i++){ printf("请输入第%d个元素的值：",i); scanf("%d",&S.base[i-1]); *(S.top++); } printf("%d个元素入栈成功\n",Num); } //这条语句的目的是为了检测栈顶指针的位置是否在栈顶元素的下一个位置//如果输出的值等于输入元素的个数，则说明此时栈顶指针和栈底指针的位置都在正确的位置 // printf("%d\n",S.top-S.base); returnOK; }
在进行批量元素入栈前，先判断栈是否存在，判断栈是否存在只需要判断栈底指针S.base是否存在即可。因为栈是一种先进后出的线性表，所以先插入的元素就会直接放到栈底，如果栈底指针不存在则说明没有开辟连续的存储空间。
确定栈存在以后接着判断栈是否为空栈
①如果当前栈不是空栈：
在刚才讲到过S.top - S.base表示当前栈中的元素个数，S.stacksize表示栈的存储空间分配量，所以当S.top - S.base > S.stacksize时表
示此时栈已满，需要再开辟一块连续的存储空间，这里用到了realloc函数，简单的介绍一下realloc函数：
realloc()函数：
作用：重新分配空间
参数：原空间基址，现需空间大小
返回值：1. 成功：新空间地址(本质上是一个数值) 2. 失败：NULL
如果此时栈没有满，此时S.top指向的是下一个元素的位置，再插入元素只需要将要批量插入元素的第一个值赋值给S.top所指向的存储空间，之后再执行S.top++即可
（在这里我定义了一个int类型的辅助数组temp[]，先将输入的值暂时存储在临时数组中）
图示：
②如果当前栈是空栈：
如果当前栈为空栈，此时栈顶指针S.top与栈底指针S.base都指向开辟的第一块存储空间，再插入元素时不需要移动S.base指针，只需要移动S.top指针确保S.top指针一直指向栈顶元素的下一个位置即可
5. 对顺序栈进行销毁
代码如下：
//对顺序栈进行销毁 StatusDistoryStack(SqStack&S) { if(!S.base){ printf("顺序栈不存在，无法销毁\n"); returnERROR; } free(S.base); //使用free函数，将之前动态分配的内存还给系统 S.stacksize=0; //将栈的存储容量重置为0S.top=NULL; //重置栈顶指针为NULL S.base=NULL; //重置栈底指针为NULLprintf("顺序栈销毁成功\n"); returnOK; }
销毁顺序栈前我进行了栈是否存在的判断，如果顺序栈不存在就直接返回ERROR
S.base中存储的是初始化是动态分配内存首元素的地址，free函数的作用就是将之前动态分配的内存还给系统，但是在调用free函数之后，虽然归还了内存，但是S.base和S.top仍然指向原来的地址，而这个地址在归还内存之后程序便无权进行访问，所以此时S.base和S.top就成了两个野指针，重置S.base和S.top为NULL就是为了防止发生野指针访问的情况，接着将顺序栈的存储容量S.stacksize重置为0
6. 对顺序栈进行重置
代码如下：
//对顺序栈进行重置 StatusClearStack(SqStack&S) { if(!S.base){ printf("顺序栈不存在，不需要进行重置\n"); returnERROR; } S.top=S.base; //将栈底指针赋值给栈顶指针 printf("顺序栈重置成功\n"); returnOK; }
重置顺序栈时只需要将栈底指针的地址赋值给栈顶指针就可以了，因为栈顶指针和栈底指针都没有指向之前赋值过的元素，而且S.top=S.base时认为栈为空栈
其次在开辟一块连续的存储地址时，地址内也存在有原本的值，所以开辟出的新的存储空间并不是空的，在之后无论是销毁栈又或者是重新给栈进行赋值时都会将之前赋给存储空间的值覆盖掉
7. 判断顺序栈是否为空
代码如下：
//判断顺序栈是否为空StatusStackEmpty(SqStackS) { if(!S.base) returnERROR; if(S.top==S.base) returnTRUE; elsereturnFALSE; }
在判断顺序栈是否为空之前仍然要先判断顺序栈是否存在，其次判断顺序栈是否为空只需要判断栈顶指针和栈底指针的位置即可，因为在元素入栈与出栈时栈底指针S.base的位置是不会发生变化，所以当S.top(栈顶指针)=S.base(栈底指针)时说明当前顺序栈为空栈，否则顺序栈不为空栈。
当顺序栈不存在时返回ERROR，顺序栈为空栈时返回TRUE，顺序栈不为空栈时返回FALSE
8. 获取顺序栈的长度
代码如下：
//获取顺序栈的长度StatusStackLength(SqStackS) { if(!S.base){ printf("顺序栈不存在，没有长度\n"); returnERROR; } intK; K=S.top-S.base; printf("栈的长度为：%d\n",K); returnOK; //返回顺序栈的长度 }
在获取顺序栈的长度之前仍然要先进行顺序栈是否存在的判断，顺序栈的长度也称顺序栈的元素个数。
在上面提到过，在顺序栈中，栈顶指针指向栈顶元素的下一个位置，S.top - S.base即为顺序栈的元素个数，在这里我定义了一个int类型的数据K，也可以在顺序栈存在的前提下直接return S.top-S.base;
9. 获取栈顶元素
代码如下：
//获取栈顶元素StatusGetTop(SqStackS) { if(!S.base){ printf("顺序栈不存在，不存在栈顶元素\n"); returnERROR; }elseif(S.base==S.top){ printf("顺序栈为空栈，不存在栈顶元素\n"); returnERROR; } inte; e=*(S.top-1); printf("栈顶元素为：%d\n",e); returnOK; }
获取栈顶元素的操作在顺序栈存在且不为空栈的前提下进行，所以先加入了顺序栈是否存在并且存在是否为空栈的判断。
因为在顺序栈中栈顶指针S.top指向的是栈顶元素的下一个位置，所以在获取栈顶元素时只需要将*(S.top-1)地址存储的值赋给一个int类型的变量e即可。
在这里可能会对代码有疑问：将S.top向下移动之后不再将S.top指针移动回原本的位置？
解答：因为在获取栈顶元素的方法中，没有使用引用传递，所以此时改变了S.top的位置并不会影响到
原本的S.top的位置
10. 插入新的栈顶元素并返回其值
代码如下：
//插入新的栈顶元素并返回其值 StatusPush(SqStack&S,SElemTypee) { if(!S.base){ printf("顺序栈不存在，无法插入新的栈顶元素\n"); returnERROR; } elseif(S.top-S.base>=S.stacksize) //此时顺序栈已满，追加存储空间 { if(!S.base){ //如果存储空间分配失败 printf("存储空间分配失败\n"); exit(OVERFLOW); } S.base= (SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT) *sizeof(SElemType)); S.top=S.base+S.stacksize; S.stacksize=S.stacksize+STACKINCREMENT; //更新栈的空间大小 } *S.top=e; S.top++; returne; //返回新插入的栈顶元素的值 }
在插入新的栈顶元素时也应该进行顺序栈是否存在的判断，只有当顺序栈存在时才能进行新的栈顶元素的插入，在顺序栈存在时向栈顶插入元素时也要进行栈是否已满的判断。因为本身栈顶指针S.top就是指向栈顶元素的下一个位置，所以只需要将要插入的元素赋值给当前S.top指向的位置，再将S.top++即可
11. 删除栈顶元素并返回其值
代码如下：
//删除栈顶元素并返回其值StatusPop(SqStack&S) { if(!S.base) return-1; elseif(S.base==S.top) return-2; SElemTypee; e=*(S.top-1); S.top=S.top-1; returne; //返回被删除的栈顶元素的值 }
删除栈底元素也是建立在顺序栈存在并且不为空的前提下进行的
先定义一个SElemType(本质上是int)类型的变量e，再将当前S.top位置存储的值赋值给e，再将栈顶指针S.top向后移一位，使之前栈顶的上一个元素成为新的栈顶便完成了栈顶元素的删除，最后再将e返回
12. 打印顺序栈
代码如下：
//打印顺序栈StatusPrintStack(SqStackS) { if(!S.base){ printf("顺序栈不存在，无法打印\n"); returnERROR; } elseif(S.base==S.top) printf("顺序栈为空栈\n"); printf("当前顺序栈的元素为："); for(inti=0;i< (S.top-S.base);i++){ printf(" %d",S.base[i]); } printf("\n"); //换行 returnOK; }
打印顺序栈也是建立在顺序栈存在的基础上，顺序栈存在时利用for循环依次将栈中存储的元素打印出来，for循环中的判断条件为S.top - S.base，循环的次数为栈中所含有的元素个数
三、简单应用的实现：
1. 括号匹配
代码如下：
//括号匹配的检验Statusexamine(char*List) { SqStackS; S.base=S.top=NULL; //将空栈的栈顶和栈底指针赋值为NULL,因为此时并未对栈进行任何操作InitStack(S); //构造一个空栈intresult; inttemp=0; intfinal=0; intlength=strlen(List); //获取字符数组的长度 charArrays[length]; //定义一个与传来的字符数组长度相等的字符数组作为辅助数组 if(length==1) { printf("输入的序列括号不匹配\n"); printf("输入的序列长度为：%d\n",length); returnERROR; } for(inti=0;i<length;i++) { switch(List[i]) //利用switch语句来控制括号的入栈和出栈 { case'(': case'[': case'{': { Arrays[i] =Push(S,List[i]); temp=1; }break; case')': case']': case'}': { Arrays[i] =Pop(S); if(Arrays[i] =='('&&List[i] !=')') //如果遇到了右括号判断是否与之前入栈的左括号对应 final=-1; //如果左括号与右括号不匹配就将final的值修改为-1 elseif(Arrays[i] =='['&&List[i] !=']') final=-1; elseif(Arrays[i] =='{'&&List[i] !='}') final=-1; } } } if(StackEmpty(S) &&temp!=1){ printf("您输入的序列中没有括号\n"); final=2; } if(temp==1&&!StackEmpty(S)){ printf("输入的序列括号不匹配\n"); printf("输入的序列长度为：%d\n",length); returnOK; } if(final==-1) { printf("输入的序列括号不匹配\n"); printf("输入的序列长度为：%d\n",length); returnOK; }elseif(final==0&&temp==1) { result=StackEmpty(S); //使用result接收判断是否为空栈的结果if(result==TRUE) printf("输入的序列括号匹配\n"); elseif(result==FALSE) printf("输入的序列括号不匹配\n"); printf("输入的序列长度为：%d\n",length); // printf("%s\n",Arrays); //这条语句用于检测出栈的顺序 } returnOK; }
括号匹配是栈的一个简单应用，在编写代码前要先想到几个问题：
- 当输入的一个序列中没有括号时
- 当只输入一个右括号时
- 左右两边的括号数目相同但是却不是配对的括号
思路：
在接收到用户从键盘输入的字符串之后调用strlen函数获取字符串的长度并赋值给int类型的数据length，利用for循环将接收到的字符串中的每一个元素进行遍历，for循环的判断条件就是刚才通过strlen函数获取到的字符串长度。
在for循环中嵌套一个switch语句，如果遇到"("，"{"，"[“就调用入栈元素将其放入到栈中，遇到”)"，"}"，"]"后就从栈中取出栈顶元素，并判断取出的左括号是否与右括号匹配，如果不匹配则输出输入的序列长度并返回不匹配。
代码解释：
函数头传来的参数是之前用户从键盘输入的一个字符串类型的数据
- 先定义一个在之后空栈用来存储括号
- 再定义了int类型的变量final和temp作为标志变量并赋初值0
- 在进入for循环之前我定义了一个if语句，作用是当接收到的字符串长度为1时，直接返回不匹配
- 定义switch语句来判断元素元素是否需要入栈，如果遇到入栈操作就将标志变量temp赋值为1。在switch语句中如果遇到出栈操作就进行判断当前出栈的元素是否与当前辅助数组中存储的右括号匹配，如果不匹配就修改标志变量final的值为-1
- 在for循环结束后加一个if判断条件，如果在循环完成时都没有进行修改temp的值（也就是说没有进行任何入栈出栈操作），说明输入的序列中不存在括号，修改final的值为2
- 最后根据标志变量的值对所有情况进行判断并输出结果
