导入
什么是栈？
栈数据结构简介，及其用途和功能。
简介
我们都熟悉几乎所有主流应用程序中都存在的“撤销”（Undo）功能。你有没有想过它是如何实现的呢？其实，其原理是将工作状态的前若干个历史版本按顺序存储在内存中，使得最近的状态排在最前面。使用普通列表很难高效地实现这一功能，具体原因我们将在后续章节中探讨。这时，“栈”这种数据结构就派上了用场。
栈遵循“后进先出”（Last In First Out, LIFO）的原则，也就是说，最后添加的元素位于栈顶，而最早添加的元素则位于栈底。
现实生活中的一个栈的例子就是一叠书。如果你想取出中间某一本，就必须先把压在上面的所有书一本本拿开。而且，你最后放上去的那本书，一定是在这叠书的最上面！
...
栈的用途
尽管栈的实现很简单，但它却能用于解决许多复杂的问题！
一些著名的算法，例如“深度优先搜索”（Depth First Search）和“表达式求值算法”（Expression Evaluation Algorithm），都充分利用了栈的特性。栈常被用于：
- 回溯到之前的状态或任务，例如在递归代码中；
- 存储尚未完成的任务，例如在图中从某个节点出发探索两条不同路径时，暂存其中一条路径的处理进度，以寻找到达目标的最短路径。
栈的工作原理
栈可以通过多种方式实现，但一个典型的栈必须提供以下基本操作：
| 函数 | 功能说明 |
|---|---|
push(element) | 将元素插入栈顶 |
pop() | 移除并返回栈顶元素 |
peek() | 返回栈顶元素（不移除） |
IsEmpty() | 如果栈为空，则返回真（1） |
size() | 返回栈中元素的数量 |
下面的动画直观地演示了 push(element) 和 pop() 操作的执行过程。