【数据结构】栈
本文更新于个人博客Burnside Blog
总的来说，栈（Stack）是一种应用十分广泛的线性数据结构，我们大多数时候可以把它理解成一个杯子，杯子只有一个口，它既是进入的入口，也是退出的出口。的确如此，栈是一种先入后出（LIFO）的数据结构，它支持插入与删除两种操作，且两个操作仅可以在一端进行。
为了方便起见，我们不使用动态方式生成一个栈，或销毁一个栈，我们只考虑一个静态的栈的功能实现。栈中的元素可以是任何的用户自定义类型，为了方便起见，我们假设元素的类型为int，如需要别的类型，只需要灵活处理即可。接下来我们申请一块长度为MaxSize的连续内存来存储这个栈，这时它又被称为顺序栈。
int Stack[MaxSize];
这样我们就成功获得了一个自己的栈。考虑往栈中插入元素或删除元素，所改变的只有最顶部的元素距栈底的距离，这里的距离表示的是元素个数，我们把这个顶部称为栈顶，可以用一个变量top来维护，最顶部的元素为栈顶元素，不难发现，每一次的删除操作，总是删除的栈顶元素。
因此，我们会得到栈的几个操作：
1、插入元素
int push(int x){
Stack[++top]=x;
return top;
}
插入一个元素很简单，只需要将栈顶指向数组内的下一个位置，然后把该位置赋值为要插入的值即可，函数中的变量x即为需要插入的值，top为栈顶，此函数返回值为插入后的栈顶。注意，当栈为空的时候，变量top应当等于-1。
2、删除元素
int pop(){
return --top;
}
删除一个元素更简单，只需要将栈顶下移一个就可以。注意，原来的栈顶元素不需要做任何的改变，因为只要插入到这个位置，这个位置就会立马被赋值上被插入的新的元素，所以只需要让栈顶下移即可，而并不需要改变栈顶元素的值。此函数返回的是删除后的栈顶。要注意，这里有一个潜在的问题，如果这个时候栈已空，但仍然调用了pop()，可能会使以后的操作访问到非法位置，因此，请务必确保栈是非空的，再使用pop()，为了方便确保栈是否为空，我们引入一个新的函数。
3、查询栈是否为空
bool empty(){
return top==-1?true:false;
}
很简单，栈为空的标志为top等于-1，直接调用即可。
4、查询栈现在的大小（size）
int size(){
return top+1;
}
也很简单，栈的大小为top+1。
5、查询栈顶元素
int top(){
return Stack[top];
}
请注意，请务必在栈非空的情况下使用该命令。
6、删除栈内的所有元素
void clear(){
while(!empty()) pop();
}
很自然的实现，当栈为非空时，一直删除元素就可以了。
以上为栈的所有操作，部分书中还介绍了链式栈，本文中不再涉及，具体的实现思想与上述六个函数一样。
栈有很多实际的应用，其中常见的有：把一个十进制数拆分为二进制，查询一个括号序列是否能够匹配，计算表达式的值等。我们主要来写查询括号序列是否匹配，剩下两个常见功能读者可以自行完成。
括号序列，是仅由(与)构成的序列，匹配的定义如下：
1. ()是一个合法匹配。
2. 如果A是一个合法匹配，则(A)是一个合法匹配。
3. 如果A和B都是合法匹配，则AB是一个合法匹配。
不难发现，()()(())((())())是一个合法匹配，而(()不是一个合法匹配。
判断的过程也很轻松，我们只需要模拟这个匹配的过程就可以了，具体操作步骤如下：
1. 如果当前读取到一个(，进栈，读取下一位。
2. 如果当前读取到一个)，如果栈非空，取栈顶的右括号与之匹配，读取下一位；如果栈空，则找不到括号与之匹配，证明其不合法。
3. 如果读完了整个括号序列栈空，则整个括号序列合法，否则不合法。
正确性显然，不过多赘述，代码如下：
#include<iostream>
#include<cstdio>
const int MaxSize=1000;
char Stack[MaxSize];
int top=-1,flag=true;
int main(){
char c;
while((c=getchar())!=EOF){
if(c=='(') Stack[++top]='(';
else{
if(top==-1){
flag=false;
break;
}
top--;
}
}
if(top!=-1) flag=false;
printf(flag?"legal":"illegal");
return 0;
}
可能会有人表示输出总是illegal，因为在一开始读的时候把回车也读进去了，可以使用文件输入输出，最后不换行就可以了，或者可以采用其他的输入方式。
在某些特殊应用中，还会使用到单调栈，因为仅在竞赛中常用，因此不在本文中描述。
