本文内容，参考自《大话数据结构》(程杰著) ，一部分自己修改，如：把C语言换成了Java语言。写作目的，意在加强记忆。
本文写作工具，使用 Typora。
栈的定义
栈是限定仅在表尾进行插入和删除操作的线性表。
就像手机弹夹中的子弹一样先进去，却要后出来，而后进的，反而可以先出来的数据结构——栈。
在我们软件应用中，栈这种后进先出数据结构的应用是非常普遍。比如你用浏览器上网时，不管什么浏览器都有一个"后退"键，你点击后可以按访问顺序的逆顺序加载浏览过的网页。很多类似的软件，比如 Word、Photoshop 等文档或图像编辑软件中，都有撤销的操作，也是用栈这种方式来实现的，当然不同的软件具体实现代码会有很大差异，不过原理其实都是一样的。
我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。
首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这是表尾是指栈顶。
它的特殊之处在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。
栈的插入操作，叫作进栈，也称为压栈，入栈。
栈的删除操作，叫作出栈，也有的叫作弹栈。
栈的顺序存储结构与实现
即然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。线性表是用数组实现的，想想看，对于栈这种只能一头插入删除的线性表来说，用数组哪一端来作为栈顶和栈底比较好？
对，没错，下标为 0 的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作栈底。
我们定义一个 top 变量来指示栈顶元素在数组中的位置，若存储栈的长度为 stackSize ，则栈顶位置 top 必须小于 stackSize 。当栈存在一个元素时，top 等于 0 ，因此通常把空栈的判定条件为 top 等于 -1。
来看看栈的结构定义，代码如下：
public class Stack { static final int MAXSIZE = 5; int top = -1;// 用于标识栈顶位置 Object[] data;// 类型根据实际情况而定，这里假设为 Object }复制代码 对于进栈操作push，其代码如下：
public boolean push(Object element) { //栈满 if(top == MAXSIZE-1) { return false; } top++;//栈顶标识加一 data[top] = element;//将新插入元素赋值给栈顶空间 return true; }复制代码 对于出栈操作pop，代码如下：
public boolean pop() { //栈空 if(top == -1) { return false; } data[top] = null;//收回内存 top--;//栈顶标识减一 return true; }复制代码 进栈、出栈都没有涉及循环语句，因此时间复杂度都是O(1)。
两栈共享空间
其实栈的顺序存储还是很方便的，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大的缺陷，就是必须事先确定数组存储空间大小，万一不够用了，就需要编程手段来扩展数组的容量，非常麻烦。对于一个栈，我们也只能尽量考虑周全，设计出合适大小的数组来处理，但对于两个相同类型的栈，我们却可以做到最大限度地利用其事先开辟的存储空间来进行操作。
举个生活中的例子，我和你一人有一瓶水，我不够喝，喝你的；你不够喝，就喝我的。
同样的道理，如果我们有两个相同类型的栈，我们为它们各自开辟了数组空间，极有可能是第一个栈满了，再进栈就溢出了，而另一个栈还有很多存储空间空闲。这又何必呢？我们完全可以用一个数组来存储两个栈，只不过需要点小技巧。
我们的做法：数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为 0 处，另一个栈为数组的尾端，即下标为数组长度 n-1 处。这样，两个栈如果增加元素，就是两端点向中间靠。
其实关键思路是：它们是在数组的两端，向中间靠拢。top1 和 top2 是栈1 和栈2 的栈顶标识，可以想象，只要它们俩不见面，两个栈就可以一直使用。
从这里也就可以分析出来，栈1 为空时，就是top1 等于 -1 时；而当top2 等于 n 时，即是栈2 为空时。
那什么时候栈满呢？
想想极端的情况，若栈2 是空栈，栈1 的top1 等于 n-1 时，就是栈1 满了。反之，当栈1 为空栈时，top2 等于 0 时，为栈2 满。其实就是我刚才说的，两个栈见面之时，也就是两个标识之间相差1 时，即 top1 + 1 == top2 为栈满。
两栈共享空间的结构代码如下：
public class ShareStack { static final int MAXSIZE = 5; int top1 = -1;//栈1 栈顶标识 int top2 = MAXSIZE;//栈2 栈顶标识 Object[] data; }复制代码 对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈1 还是栈2 的栈号参数stackType。插入元素的代码如下：
public boolean push(Object element,int stackType) { //栈满，不能再push新元素 if(top1+1 == top2) { return false; } if(stackType == 1) { //栈1 有新元素入栈 data[++top1] = element;//若栈1 则先top1+1 后给数组元素赋值 } else if(stackType == 2) { //栈2 有新元素入栈 data[--top2] = element;//若栈2 则先top2-1 后给数组元素赋值 } return true; }复制代码 对于两栈共享空间的pop方法，参数就只是判断栈1 栈2 的参数stackType，代码如下：
public boolean pop(int stackType) { if(stackType == 1) { if(top1 == -1) { return false; } data[top1] = null; top1--; } else if(stackType == 2) { if(top2 == MAXSIZE) { return false; } data[top2] = null; top2++; } return true; }复制代码 事实上，使用两栈共享空间这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。
栈的链式存储结构与实现
说完了栈的顺序存储结构，我们现在来看看栈的链式存储结构，简称为链栈。
想想看，栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？由于单链表有头指针，而栈顶指针也是必须的，那干嘛不让它们合二为一呢，所以比较好的办法是把栈顶放在单链表的头部。另外，都已经有了栈顶在头部了，单链表中比较常用的头结点也就没有意义了，通常对于链栈来说，是不需要头结点的。
对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间。
但对于空栈来说，链表原定义是头指针为空，那么链表的空其实就是 top = NULL。
链栈的结构代码如下：
public class StackNode { int data; StackNode next; }复制代码 public class LinkedStack { int count; StackNode top; }复制代码 链栈的进栈操作，代码如下：
public boolean push(int element) { StackNode node = new StackNode(); node.data = element;//把当前的栈顶元素赋值给新结点的直接后继 node.next = top;//将新的结点 S 赋值给栈顶指针 top = node; count++; return true; }复制代码 链栈的出栈操作，代码如下：
public boolean pop() { if(count == 0) { return false; } StackNode node = top;//将栈顶赋值给node top = top.next;//使栈顶指针下移一位，指向后一结点 node = null;//释放结点node count--; return true; }复制代码 进栈、出栈都没有涉及循环语句，因此时间复杂度都是O(1)。
对比一下顺序栈和链栈，它们在时间复杂度上都是O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时很大，那么最好是用链栈，反之，建议使用顺序栈会更好一些。