3个整型数字元素1、2、3依次进栈，会有5种出栈次序：

1) 1,2,3进，3,2,1出。出栈次序为321.

2) 1进1出，2进2出，3进3出。出栈次序为123.

3) 1进，2进2出，3进3出，1出。出栈次序为231.

4) 1进，2进，2出，1出，3进3出。出栈次序为213.

5) 1进，1出，2进，3进，3出，2出。出栈次序为132.

 

上一章讨论了线性表的顺序存储和链式存储，对于栈来说，也是同样适用的。

 

栈是线性表的特例，栈的顺序存储其实是线性表顺序存储的简化，简称为顺序栈。

 

top1=-1时，栈1为空；top2=n时，栈2为空。当top1+1=top2时，栈满。

 

使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时，即一个栈增长时另一个栈在缩短的情况。

 

 

栈的链式存储结构，简称为链栈。

如果栈的使用过程中元素变化不可预料，则用链栈；反之，如果元素的变化在可控范围内，则用顺序栈。

栈的引入简化了程序设计的问题，划分了不同的关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题的核心。

 

 

把一个直接调用自己或通过一系列的调用语句间接调用自己的函数，称作递归函数。

每个递归定义必须至少有一个条件，满足时递归不再进行。

 

迭代和递归的区别：

1. 迭代使用的是循环结构，递归使用的是选择结构。

2. 递归能使程序的结构更清晰，但大量的递归调用会建立函数的副本，消耗大量的时间和内存；迭代不需要反复调用函数和占用额外的内存。

 

存储某些数据，并在后面又以存储的逆序恢复这些数据，以提供之后使用的需求，显然很符合栈这样的数据结构。

 

在递归的前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中；在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。

 

 

四则运算中括号成对出现，碰到左括号，就将此左括号进栈，不管表达式有多少重括号都如此，碰到左括号就将此左括号进栈。后面出现右括号时，就让栈顶的左括号出栈，期间让数字运算。这样，最终有括号的表达式从左到右巡查一遍，栈应该是由空到有元素，最终再因全部匹配成功后成为空栈的结果。

 

后缀表达式：所有的符号都在运算数字的后面出现。

比如：9+(3-1)*3=10/2 化为后缀表达式为：9 3 1 - 3 * + 10 2 / +

 

后缀表达式：9 3 1 - 3 * + 10 2 / +

规则：从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到符号就将处于栈顶的两个数字出栈，一直到最终获得结果。

 

平时所用的标准四则运算表达式叫做中缀表达式。

规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号则栈顶元素一次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。