栈

概述

栈（Stack） 是一种遵循**后进先出（Last-In-First-Out, LIFO）**原则的动态集合。最后被压入（push）的元素将最先被弹出（pop），类似于桌上的一叠盘子——只能从顶部放入或取出。

定义

栈（Stack）

栈 $S$ 是一个支持以下操作的动态集合，其中属性 $S.top$ 指向栈中最新插入的元素：

• $\text{textsc}Stack-Empty(S)$：若 $S.top=0$，返回 $\text{TRUE}$；否则返回 $\text{FALSE}$。
• $\text{textsc}Push(S,x)$：$S.top\leftarrow S.top+1$；$S[S.top]\leftarrow x$。
• $\text{textsc}Pop(S)$：若 $\text{textsc}Stack-Empty(S)$ 则报错 underflow；否则 $S.top\leftarrow S.top-1$，返回 $S[S.top+1]$。

栈可以用数组 $S[\mathrm{1..}n]$ 实现，其中 $n$ 为栈的最大容量。$S.top$ 是一个整数索引，初始值为 $0$，表示栈为空。

核心性质

• LIFO 原则：元素的出栈顺序与入栈顺序严格相反。
• 操作复杂度：$\text{textsc}Push$、$\text{textsc}Pop$、$\text{textsc}Stack-Empty$ 均为 $O(1)$ 时间。
• 容量限制：数组实现需要预先分配固定大小 $n$，当 $S.top=n$ 时发生 栈溢出（stack overflow）。
• 仅顶部可访问：栈不提供对中间或底部元素的直接访问。

操作示例

操作	栈内容（底→顶）	$S.top$
初始	—	0
Push(4)	4	1
Push(1)	4, 1	2
Pop() → 1	4	1
Push(3)	4, 3	2

章节扩展

第10章：基于数组的实现

栈是 CLRS 第10章介绍的第一个基于数组的数据结构。其实现核心在于用数组索引 $S.top$ 追踪栈顶位置，所有操作仅涉及对 $top$ 的增减和数组的一次读写，因此每个操作均为常数时间。

栈在算法中有广泛应用：深度优先搜索（DFS）的递归调用栈、括号匹配、表达式求值、后缀表达式计算等。

第20章：基本图算法

DFS的递归实现隐式使用系统调用栈：每深入一层递归对应入栈，回溯对应出栈。栈深度最大为 O(V)。拓扑排序算法在DFS完成后，将顶点按完成时间逆序压入栈中（或链表头部插入），最终弹出顺序即为拓扑序。

参见

• 队列 — 同为线性受限结构，但遵循 FIFO 原则
• 链表 — 栈也可以用链表实现，无需预分配容量
• 二叉堆 — 对比：堆同样基于数组实现，但支持更复杂的优先级操作