数据结构——线性结构（1）——顺序栈结构

在说什么是线性结构之前，我想还是先提前学习具体的结构，然后再一一总结为好。 栈（stack）应该是线性结构中容易的一种数据结构了，这种结构的主要操作有两种：将一个新的值添加到栈称为推送（push）该值; 删除堆栈中的顶层的值称为弹出（pop）栈。以后我们就直接用英文来表示了。在stack中这种的顺序处理方式我们通常称为LIFO，意思是后进先出。

栈的模型

我们用下面的模型来模拟栈的这个结构： 假设你在一个自助餐厅，客人在自助餐线上开始时拿起自己的盘子，那些盘子就放在弹簧柱上，这样子是为了方便顾客从自助餐线上拿起顶部的盘子，就像下图的模式那样：

当放碗机添加新的盘子时，它会放在堆叠的顶部，推动弹簧的压缩，其他的略微下降，如图所示：

对于顾客来说，他们只能从stack的顶部取走盘子，一旦当他们这么做之后，其余的盘子就会弹回原来的位置上去。因此，后加进来的盘子就是个被取走的盘子。 stack在编程中如此重要还有一个小原因，那就是嵌套函数（nested function）的调用形式就是以这种方式进行的。举个例子，如果main函数中我们调用f函数，那么一个f函数的栈框架就会放在main函数栈框架的顶部，就像这样：

如果f函数中还调用了g函数，那么就会在f的栈框架（stack frame）的上方为g函数开辟一个全新的栈框架。就像这样：

当g函数返回的时候，它的栈结构就会被pop回f函数中，同样的f函数也会pop会main函数中，终返回初始的模式。 所以总结起来就是：

调用顺序（入栈）：
main -> f()->g();
返回顺序（出栈）：
g() -> f() ->main;