栈（LIFO）简介

简介

每个人都熟悉著名的“撤销”功能，几乎所有的流行应用程序中都有这个选项。但你有没有想过它是如何实现的？其实，原理是将工作之前的若干状态（数量有限）按顺序存储在内存中，使得最近的一个状态排在最前面。由于后续章节会详细探讨原因，因此使用普通的数组无法高效实现这一点。这时，“栈”这种数据结构就派上用场了。

栈遵循后进先出（LIFO） 的原则。这意味着最后加入的元素位于栈顶，而最先加入的元素则在栈底。

一个现实生活中的栈的例子就是一摞书。如果你想取出中间某本书，就必须先把上面的所有书都拿走。同样，你最后放上去的那本书就在最上面！

栈有什么用途？

尽管实现简单，栈却能解决许多复杂的问题。

许多著名算法，如深度优先搜索和表达式求值算法，都利用了栈的功能。栈常用于：

• 回溯到之前的任务或状态。例如，在递归代码中进行回溯。

• 保存一个尚未完成的任务；例如，从某个点出发探索图中的两条不同路径，同时寻找到达目标的最短路径。

栈是如何工作的？

栈可以通过多种方式实现，但一个典型的栈必须具备以下功能：

下面的动画展示了 push(value) 和 pop() 函数的高层次操作过程。