栈是一种特殊的线性表，是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。栈顶的当前位置是动态的，对栈顶当前位置的标记称为栈顶指针。当栈中没有数据元素时，称之为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常称为退栈或出栈。
在生活中常见到这样的例子：假设餐厅里有一叠盘子，如果要从中拿取盘子，只能从最上面一个开始拿，当要再放上一个盘子时也只能放在最上面。栈的结构正是如此。根据栈的定义，每次进栈的数据元素都放在原当前栈顶元素之前而成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素。这样，最后进入栈的数据元素总是最先退出栈，因此，栈具有“后进先出”（LIFO：First In Last Out）的特性。
图5.8是一个栈的动态示意图，图中箭头代表当前栈顶指针位置。图5.8(a)表示一个空栈；图5.8（b）表示插入一个数据元素 A以后的状态；图5.8（c）表示插入数据元素 B、C以后的状态；图5.8（d）表示删除数据元素C以后的状态；图5.8（e）表示删除数据元素 B、A以后的状态。简言之，若进栈顺序为A、B、C，则退栈顺序为C、B、A。图5.8显示的是一个顺序存储结构的栈，栈也可以用链式存储结构存储。

?????????????????????????? 图5.8栈的动态示意图
??? 栈的应用非常广泛，表达式求值、递归过程实现都是栈应用的典型例子。下面简单讨论一下高级语言中的表达式处理是怎样通过栈实现的。
在用高级语言编写程序时，经常写出各种类型的表达式：算术表达式、关系表达式和逻辑表达式等等。编译系统在处理表达式时，需要将表达式翻译成机器指令序列，这首先需要确定运算次序。为此，需要建立两个栈——操作数栈（ODS）和操作符栈（OPS），然后自左至右扫描表达式。为叙述简洁，仅讨论算术表达式的计算，且假设表达式中只含有加、减、乘、除四种运算符和左、右圆括号，一个表达式用“#”作为分界符标识表达式的结束，并将表达式中自左至右所读到的一个操作数或一个操作符称为“一个词”。用栈实现表达式求值的处理过程如下：
（1） 读入一个词；
（2） 判断该词是操作数还是操作符，如果是操作数，则将该操作数压入ODS栈并转第（1）步；否则继续往下；
（3） 判断表达式是否结束，是结束符则转第（7）步，否则继续往下；
（4） 判断当前操作符优先级是否大于或等于OPS栈顶操作符的优先级（左括号的优先级最高，其次是乘除，再是加减，右括号的优先级最低）或者OPS栈是否为空，如果是，当前操作符压入OPS栈并转第（1）步；否则，继续往下；
（5） 从ODS栈中弹出两个操作数Y和X，从OPS栈中弹出一个操作符θ，进行运算XθY，并将结果压入ODS栈。需要说明的是，如果当前操作符是右括号，则重复第（5）步这一过程，直到OPS栈顶操作符为左括号；
（6） 当前操作符压入OPS栈（如果当前操作符是右括号，则它不但不压入OPS栈中，相反还从OPS栈中弹出左括号，这称为去括号）后，转第（1）步；
（7） 判断OPS栈是否为空，不是，则从ODS栈中弹出两个操作数Y和X，从OPS栈中弹出一个操作符θ，进行运算XθY，并将结果压入ODS栈；
（8） ODS栈顶的值即为所求表达式的值，求值过程结束。
利用栈处理算术表达式a×（b-d/e）+f的过程如下图5.9所示。
图5.9（a）表示了依次读入表达式中的“a”、“”、“（”、“b”、“-”、“d”、“/”、“e”等单词后操作数栈ODS（图示的左边）和操作符栈OPS（图示的右边）的状态；图5.9（b）和图5.9（c）表示了读入“）”后，去括号的过程，其中t1=d/e，t2=b-t1；图5.9（d）表示了读入“+”后，ODS和OPS的状态，其中t3=at2；图5.9（e）表示了读入“f”后，ODS和OPS的状态；图5.9（f）表示了读入表达式结束符后，ODS和OPS的状态，其中t4=t3+f，此时操作符栈OPS为空，操作数栈ODS的栈顶元素t4就是所求的表达式的值。

图5.9利用栈处理表达式a*（b-d/e）+f的示意图
转载自：http://public.whut.edu.cn/comptsci/web/data/513.htm