形式陈述

栈支持 push(x)、pop()、top()，并满足后进先出：若在无中间删除时依次压入 $x_1,\dots ,x_k$，则弹出顺序为 $x_k,\dots ,x_1$。空栈上 pop 或 top 的行为必须由规格明确。

直觉

所有更新集中在同一端，最后进入的元素最先离开。栈的关键是可观察顺序，而不是使用数组还是链表。

例子与边界

括号匹配时，遇左括号压栈，遇右括号检查并弹出最近未匹配的左括号。调用栈记录嵌套函数活动。若允许从中间任意删除，就不再是纯栈接口。

推论与应用

深度优先搜索、表达式求值、回溯和递归运行时都使用栈。不同实现可有不同空间和缓存成本，但应满足同一 LIFO 规律。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, §10.1。
• Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., Addison-Wesley, 2011, §1.3。