导入
什么是栈？
在本节课中，我们将介绍栈这种数据结构，以及它的用途和基本功能。
简介
我们都熟悉几乎所有应用程序中都存在的著名“撤销”（Undo）功能。你有没有想过它是如何实现的？其核心思想是将工作状态的先前版本（通常限制为特定数量）按顺序存储在内存中，使得最近的状态最先被访问。这仅用数组难以高效实现，因此栈（Stack）就派上了用场。
你可以把栈想象成一个容器，只能从顶部添加或移除元素。也就是说，最先放入的元素必须等到后面的所有元素都被取出后才能被取出，而最后放入的元素则可以最先被取出。这种特性被称为后进先出（LIFO, Last In First Out） 的顺序。
现实生活中的栈的一个例子就是垂直堆放的一摞书。如果你想取出中间某一本，就必须先把压在它上面的所有书拿走。这就是 LIFO 机制的工作方式。下图展示了一个栈的结构：
栈的用途有哪些？
栈是最基础的数据结构之一，实现简单却能解决许多复杂问题。
许多计算机算法，例如深度优先搜索（Depth First Search）和表达式求值算法（Expression Evaluation Algorithm），都依赖于栈来正确运行。栈常用于以下场景：
- 回溯到之前的任务或状态，例如在递归代码中；
- 存储尚未完成的任务，例如在图中从某个点出发探索两条不同路径以寻找最短路径时。
栈是如何工作的？
栈可以通过多种方式实现，但一个典型的栈应提供以下基本操作：
| 函数 | 说明 |
|---|---|
push | 在栈顶插入一个元素 |
pop | 移除栈顶元素并将其返回 |
isFull | 如果栈已满则返回 true，否则返回 false |
isEmpty | 如果栈为空则返回 true，否则返回 false |
top | 返回栈顶元素（即最近添加的元素） |
栈的所有功能都依赖于表中列出的 push 和 pop 方法。下面的动画演示了如何向栈中依次 压入 元素，然后再逐个 弹出。
说明
当向栈中插入元素时，用于记录栈顶位置的变量原本指向当前栈顶元素。因此，每次插入新元素后，都需要更新该变量的值。同样地，在删除元素时，该变量的值也需要相应改变。良好的编程习惯是：先更新 top 变量，再执行插入或删除操作；否则，在插入时变量可能会指向空地址或错误的位置。