数据结构学习笔记——栈

定义

栈（stack）：是限定仅在表尾进行插入和删除操作的线性表。

我们允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。

栈又称作后进先出（Last In First Out）的线性表。这里应该注意，栈是一种特殊的线性表。栈的特殊之处在于限制了线性表的插入和删除的位置。

栈是线性表，那么就具有线性关系，即前驱后继关系。

栈底是固定的，最先进栈的只能在栈底。

栈的插入操纵，叫做进栈，也叫压栈、入栈。栈的删除操作，也叫出栈，有的也叫弹栈。如图：

特殊注意，并不是最先进栈的就一定是最后出栈，如1进、1出、2进、2出、3进、3出，1先进，1也先出。

线性表的顺序存储和链式存储，对于栈来说同样适用。

栈的顺序存储结构

栈是通过数组来实现的。如图：

top表示栈顶元素的位置，top为-1表示为空栈，top=StackSize-1表示栈满。

进栈、出栈

由图可知，两者都没有涉及到任何循环操作，因此时间复杂度都是O(1) 。

两栈共享控件

栈有一个很大的缺陷，就是必须事先确定数组存储空间的大小，万一不够用了，就需要用编程手段进行扩展数组容量。

对于两个相同类型的栈，我们可以尽最大限度地利用事先开辟好的存储空间来进行操作。

方法就是：两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈底为数组的末端，即下标为数组长度n-1处。这样，如果两个栈增加元素，就是两个端点向中间延伸。

top1和top2是栈1和栈2的两个栈顶指针，只要它们不见面，两个栈就可以一直用。

一般是当两个栈的空间需求有相反关系时，也就是一个栈增长，另一个栈缩短的情况。

栈的链式存储结构

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

由于单链表有头指针，而栈顶指针也是必须的，所以最好的办法就是把栈顶放在单链表的头部。如图：

对于链栈来说，基本不存在满栈的情况，除非内存已经没有可以使用的空间。

链栈的进栈和出栈

直接看图:

进栈

新结点S指针域指向原栈顶，将S赋值给栈顶指针。

出栈

栈顶结点指针指向下一位，释放结点P。

综上，如果栈的使用过程中，元素变化不可预料，有时很小，有时非常大，那么最好用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈更好。

栈的应用——递归

递归函数：我们把一个直接调用自己或者通过一系列的调用语言间接地调用自己的函数，叫做递归函数。

当然，写程序最怕陷入无限循环，所以，每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。

那么递归和栈有什么关系呢？

递归过程退回的顺序是它前进顺序的逆序。在退回过程中，可能要执行某些动作，包括恢复在前行过程中存储起来的某些数据。

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

简而言之，递归过程的退回顺序就是前进顺序的逆序，所以使用栈是最好的数据结构。