面试题-数组、链表实现栈

先来看看什么是栈，摘自百科：

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

其实栈就是一种特殊的数据结构，就像一叠盘子，一个落着一个，洗干净的盘子放到最上面，想取盘子的时候也是从最上面(top)去取。包含入栈(push)和出栈(pop)两个操作，特点是后进先出，先进后出。

数组实现栈（顺序栈）：

链表实现栈（链式栈）：

通过以上两种方式的实现，数组方式实现栈存在一个问题，容量是定义好了，如果超限需要考虑扩容问题，实现的方式一般是申请更大的空间，然后将老数组中的元素拷贝到新数组中，链式栈则不存在这个问题。

栈的实际应用：

1.浏览器的前进、后退功能，通过定义两个栈，把浏览的页面依次压入栈，当回退时，元素出栈放入到另一个栈中，当前进时，再从这个栈中取出放入到第一个栈。

2.方法的递归调用，最开始调用的方法最后执行，同样的道理。