栈ADT

栈（stack）是限制插入和删除操作只能在一个位置上进行的表，该位置是表的末端。称为栈的顶（top）。对栈的基本操作是push（进栈）和pop（出栈），前者相当于插入，后者则是删除最后插入的元素。
*对空栈进行pop或top操作，在栈中一般认为是一个错误。
*当运行push时在空间之外操作是实现限制，但不是ADT错误。

栈，LIFO（后进先出）表。

栈的实现（栈是一个表，任何实现表的方法都能实现栈。）
栈的链表实现（用单向链表）
。。。 。。。
栈的数组实现
每个栈有一个theArray和一个topOfStack，对于空栈topOfStack的值为-1。将某个元素压入栈中时，将topOfStack加1，然后置theArray[topOfStack]=x，弹出栈元素时，置pop函数的返回值为theArray[topOfStack]，然后将topOfStack减1。

应用
1.平衡符号

2.后缀操作符（逆波兰记法）当一个表达式一后缀记法给出的，没有必要知道任何优先规则。
3.中缀到后缀的转换。
4.函数调用。

参考Mark Allen Weiss《数据结构与算法分析c++描述》第三版，仅供学习交流之用，转发请注明原出处。