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