导入
栈（Stack）
栈数据结构的简介、用途及其功能。
简介
我们都很熟悉几乎所有流行应用程序中都存在的“撤销”功能。你是否曾好奇过它是如何实现的？其实，系统会将工作状态的前一时刻（数量有限）按顺序存储在内存中，使得最近的状态排在最前面。如果使用普通的数组来实现这一点，效率会很低，原因我们将在接下来的章节中详细探讨。这时，栈（Stack）数据结构就派上用场了。
栈遵循后进先出（LIFO） 的原则。这意味着最后加入的元素位于栈顶，而最早加入的元素则在栈底。
一个现实生活中的栈的例子是书堆。如果你想取到中间某本书，就必须先把上面所有的书都拿走。同样，你最后放入书堆的那本书，正好在最上面！
...
栈有什么用途？
尽管实现简单，栈却能解决许多复杂的问题！
许多著名的算法，如深度优先搜索和表达式求值算法，都利用了栈的功能。栈常用于：
- 回溯到之前的任务或状态，例如在递归代码中
- 保存一个尚未完成的任务，例如在图中从某个点出发探索两条不同路径时，用来寻找到达目标的最短路径
栈是如何工作的？
栈可以通过多种方式实现，但一个典型的栈必须具备以下功能：
| 函数 | 作用说明 |
|---|---|
push(value) | 将元素插入栈顶 |
pop() | 移除栈顶元素并返回该元素 |
isEmpty() | 若栈为空，返回布尔值 1（真） |
getTop() | 返回最近添加的元素 |
下图是一个关于 push(value) 和 pop() 函数的高层次演示动画。