#### 3、栈
栈是一种’操作受限’的线性表，只允许在一端插入和删除数据，并且满足后进先出，先进后出的特性。

#### 3.1 如何用数组来实现一个栈 ？
实际上，栈既可以用数组来实现，也可以用链表来实现，分别叫做顺序栈和链式栈。点击[顺序栈](https://github.com/gaoshengnan/LeetCode/blob/master/src/main/java/stack/ArrayStack.java)查看具体代码及注释实现。

#### 3.2 支持动态扩容的顺序栈
通过在底层依赖一个支持动态扩容的数组来实现一个可以动态扩容的顺序栈，当栈满了之后，我们就申请一个更大的数组，将原来的数据搬移到新数组中。

对于出栈操作，不涉及内存的重新申请和数据的搬移，所以出栈的时间复杂度仍是O(1)，对于入栈来说情况就不一样了，当栈中有空闲空间时，入栈的操作时间复杂度是O(1)，但当空间不够时，就需要重新申请内存和数据搬移，时间复杂度就变成了O(n)。

也就是说，对于入栈操作来说，最好时间复杂度时O(1)，最坏情况时间复杂度时O(n)

#### 3.3 如何实现浏览器的前进、后退功能 ？
我们使用两个栈X、Y来实现，首先把浏览的页面a-b-c依次压入栈X，当点击后退按钮时，再依次将c-b-a从X中出栈，并将出栈的数据依次放入栈Y中，当点击前进按钮时，再依次从Y中取出数据a-b-c，放入X中，当X中没有数据时，那就说明没有页面可以继续后退浏览了，当栈Y中没有数据，那就说明没有页面可以前进浏览了

---