数据结构--栈

栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行，也就是说只能在栈顶进行插入（push进栈）和删除（pop出栈）操作，进栈出栈的复杂度均为O(1)，栈中的数据元素遵守”先进后出"(First In Last Out)的原则，简称FILO结构。

image
image

可以看到在压栈的过程中，栈顶的位置一直在”向上“移动，而栈底是固定不变的。出栈的顺序与入栈时相反，这就是所谓的”先入后出“。在出栈的过程中，栈顶位置一直在”向下“移动，而栈底一直保持不变。
栈既然是一个表，因此任何实现表的方式都能实现栈（数组、链表（单向链表、双向链表或循环链表））。

栈的数组实现

image

栈的数组实现相对流行和简单，但唯一的潜在危害是需要提前声明一个数组大小。为了防止数组越界，可以在栈的程序中加入数组越界的检查，但他们会影响栈的执行效率。

栈的链表实现

image

以链表头为作为栈顶，这样方便节点的插入与删除。压栈产生的新节点将一直出现在链表的头部。这种实现方法的缺点在于分配和释放内存的开销比较大。

什么场景会用到栈呢？
计算器，涉及运算先后顺序，涉及计算状态的保存，通过栈能够容易的实现，把表达式转化为后缀表达式（也可以通过栈来实现），遇到数时压栈，遇到运算符时，出栈两个数并通过运算符计算。
汉诺塔的问题也可以通过栈来解决。