1什么是栈？
后进者先出，先进者后出，是典型的“栈”结构。
就像放盘子，我们是一个一个往上放，取的时候是从上到下一个一个来取。
从它的操作特性来看，它可以说是一种“操作受限的线性表”，只允许在一端进行插入和删除操作。
虽然数组和链表可以代替栈，但是它们暴露在外的操作接口过多，使用的时候比较不可控，容易发生错误。
特定的数据结构是对特定场景的抽象，当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。
2如何实现一个栈
栈既可以用数组实现也可以用链表实现，用数组实现的栈叫顺序栈，用链表实现的栈叫链式栈。
用数组实现了一下，代码如下：
我的github：OperatingStack.java
那么它的时间复杂度和空间复杂度是什么呢？
时间复杂度是O(1)，不论是入栈还是出栈，都只涉及了栈顶元素的操作。
空间复杂度也是O(1)，只需要一个大小为n的数组和几个临时变量。
3支持动态扩容的顺序栈
支持动态扩容的数组：数组满了之后，申请一块更大的空间（2倍大的空间），将原来的数据拷贝进去。
支持动态扩容的顺序栈，只需要底层依赖一个支持动态扩容的数组即可。
原理如下图：
对于入栈来说，它的时间复杂度是多少呢？
当栈内有空闲空间时，为O(1)，当栈满时，需要数据搬移，就变成了O(n)，但是它的均摊时间复杂度依然是O(1)。因为，（假设栈原先的大小为k），当栈满后，申请了一个大小为2k的新的数组，然后对栈中的k的元素进行搬移，时间复杂度为O(n)，但是在新的大小为2k的栈中，它的后面k-1个元素入栈时空间都是足够的，无需重新申请新的空间和数据搬移，所以均摊下来，时间复杂度是O(1)。
这个例子也印证了前面讲的一个道理，最好时间复杂度一般都等于均摊时间复杂度。
在大多数情况下，入栈操作的时间复杂度都是O(1)，只有极个别情况下才会退化成O(n)，我们把耗时比较多的操作的时间复杂度均摊到耗时少的上，平均情况下的时间复杂度就接近O(1)。
4栈在函数调用中的应用
操作系统为每个线程都分配了一块内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量以栈帧的形式入栈，当被调用函数执行完成，返回之后，它所对应的栈帧出栈。
以下图的代码为例：
函数调用栈的过程：
5栈在表达式求值中的应用
对于算数表达式求值，编译器是通过两个栈来实现的。其中一个保存操作数的栈，一个保存操作符的栈。将算数表达式从左到右遍历，遇到数字则压入操作数栈，遇到操作符则与操作符栈顶元素相比较，若优先级比操作符栈顶元素高，则压入操作符栈，若优先级比操作符栈顶元素低或者相同，则取出操作符栈顶一个符号和操作数栈顶两个数字进行运算，结果压入操作数栈，然后继续向下遍历。
以3+5*8-6为例，它的计算过程如下（我补充了其中省略的一小步）：
6栈在括号匹配中的应用
我们还可以用栈来检查括号的匹配。
比如{[{}]}或 [{()}([])] 等都为合法格式，，而{[}()] 或 [({)] 为非法的格式。
从左到右依次遍历括号，遇到左括号则压入栈中，遇到右括号则从栈顶取出一个左括号进行匹配，若可以匹配则继续遍历，若不能匹配或者栈中没有元素则说明它为非法格式。所有的括号都遍历完之后，若栈中为空则为合法格式，若栈中还有元素则为非法格式。
7栈实现浏览器的前进和后退功能
用两个栈X和Y来实现，按照浏览网页的顺序将它们依次压入X栈中，当点击后退时，依次从X栈中取出元素并依次压入Y中，当点击前进时，则依次从Y中取出元素并依次压入X。当X/Y为空时，说明没有数据可以后退/前进浏览了。
举例：
依次浏览了a,b,c三个网页，则将它们依次压入X栈中。
点击两次后退回到a页面，则c，b页面依次出栈，并依次压入Y栈中。
点击前进查看b页面，则b出栈，压入X栈中。
从b页面又进入了新的页面d，这个时候就无法再使用前进、后退功能来浏览c页面了，因此清空Y栈。
内容小结
栈是一种操作受限的数据结构，只支持入栈和出栈操作。后进先出是它最大的特点。栈既可以通过数组实现，也可以通过链表来实现。不管基于数组还是链表，入栈、出栈的时间复杂度都为 O(1)。除此之外，需要重点掌握支持动态扩容的顺序栈的均摊时间复杂度分析方法。
思考
1.为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？
2.我们都知道，JVM 内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用，堆内存用来存储 Java 中的对象。那 JVM 里面的“栈”跟我们这里说的“栈”是不是一回事呢？如果不是，那它为什么又叫作“栈”呢？
网友评论