栈和队列的定义与基本概念

2026 大纲 三（一）栈和队列的基本概念（与存储方式无关的那一层；顺序实现见三（二），链式实现见三（三））。

加一条限制，换来什么

栈和队列都是操作受限的线性表——它们的逻辑结构仍然是"一对一"，受限的是运算，不是元素之间的关系。

• 栈只允许在一端插入和删除。允许操作的那端叫栈顶（top），另一端叫栈底（bottom），特性是 LIFO（后进先出）。
• 队列只允许一端插入、另一端删除。插入端叫队尾（rear），删除端叫队头（front），特性是 FIFO（先进先出）。

限制换来的是可预期性，代价是能产生的输出变少。这条主线贯穿整章：

结构	插入位置	删除位置	输出序列种数（输入固定为 $1..n$）
线性表	任意位置	任意位置	$n!$
双端队列	两端均可	两端均可	介于受限双端队列与 $n!$ 之间
输入/输出受限双端队列	见《双端队列》	见《双端队列》	严格多于栈
栈	栈顶	栈顶	卡特兰数 $C_n$
队列	队尾	队头	$1$

🔴 限制越多，能产生的输出序列越少。 最极端的是队列：出队序列是唯一的——给定入队顺序，出队序列只能是它本身。FIFO 每一步能出哪个元素是被完全确定的，不给任何选择，所以"合法出队序列判断"这类问题根本不存在。栈之所以有得可考，正因为它每一步都有"弹还是不弹"这个选择。

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图3.1 栈，p88

图里箭头只画在 top 一侧：进和出用的是同一个口。栈底元素 $a_1$ 一旦被压进去，在它上面的 $a_2\sim a_n$ 全部弹出之前，它永远拿不到——这就是"后进先出"的几何解释。队列则是两个口各管一头：

出队 ← [a₁][a₂][a₃][a₄] ← 入队
       队头            队尾

有两处边界要先立好，后面每一篇的代码都建立在它们之上：

• 🔴 Pop 与 GetTop 的前置条件是"栈非空"。 "栈空时 pop"不是"返回一个特殊值"，而是违反了操作的定义域。实现代码第一行的 if (栈空) return false; 是在落实这条前置条件，不是健壮性点缀。
• 求长度不一定是 $O(1)$。 顺序栈用 top+1 直接算得出来；链栈不额外维护计数器就得遍历，$O(n)$。凡是问"某操作复杂度是多少"，先问"用什么存储结构实现"。

🔴 另外别把两层混起来：栈是逻辑结构上的约定，同一个栈可以用数组（顺序栈）也可以用链表（链栈）实现，LIFO 不变；反过来"用数组"也不等于"是栈"——顺序表同样用数组，但它允许在中间插入。由此还能分清两种溢出：下溢（空栈 pop）是逻辑层面的，链栈也有；上溢只在顺序存储下出现，链栈不存在。

栈与队列的完整基本操作集（想核对 ADT 定义与每个操作的前置条件就展开）

严蔚敏教材 ADT Stack / ADT Queue 给出的操作集：

操作	栈	队列	前置条件	时间复杂度
构造空结构	InitStack(&S)	InitQueue(&Q)	—	$O(1)$
判空	StackEmpty(S)	QueueEmpty(Q)	已存在	$O(1)$
插入	Push(&S, e)（栈顶）	EnQueue(&Q, e)（队尾）	已存在	$O(1)$
删除并返回	Pop(&S, &e)（栈顶）	DeQueue(&Q, &e)（队头）	已存在且非空	$O(1)$
只读端元素	GetTop(S, &e)，不修改栈顶指针	GetHead(Q, &e)，不修改队头指针	已存在且非空	$O(1)$
求元素个数	StackLength(S)	QueueLength(Q)	已存在	取决于实现
清空	ClearStack(&S)	—	已存在	取决于实现

出栈序列：怎么判定合不合法

先破除一个误解：题目说"元素 $1,2,\dots ,n$ 依次入栈"，指的是入栈的相对顺序是 $1,2,\dots ,n$，不是"先把 $n$ 个元素全压进去再往外弹"。入栈和出栈可以任意交错，只要满足两条：每个元素恰好入栈一次、出栈一次；任何时刻已出栈个数 $\le$ 已入栈个数。

把入栈记作 +1、出栈记作 -1，一个合法的操作序列就是一条从 0 出发、每步 ±1、全程不低于 0、终点回到 0 的折线——这正是卡特兰数的标准模型，下一节要用。

方法一：模拟（万能，首选）。 给定目标出栈序列 $\sigma ={\sigma }_1{\sigma }_2\cdots {\sigma }_n$，用一个栈从头模拟：

1. 若栈顶元素等于当前要输出的 ${\sigma }_t$，则弹出，$t++$；
2. 否则从输入 $1,2,\dots ,n$ 中把下一个还没入栈的元素压入；
3. 若输入已用尽而栈顶仍不等于 ${\sigma }_t$，判定不合法。

这个贪心是正确且唯一的：某一步能弹就必须弹——若不弹，栈顶元素会被后续入栈的元素压住，而 ${\sigma }_t$ 之后所有位置的值都要在它之后输出，栈顶就再也不可能在正确的时刻露出来。

模拟的过程里顺手能拿到另一个常被问的量：过程中栈内元素的最大个数，也就是这个出栈序列所需要的最小栈容量。

方法二：禁用模式（一眼看出，用来复核）。 排列 $\sigma$ 是合法出栈序列，当且仅当不存在下标 $i<j<k$ 使得

$${\sigma }_j<{\sigma }_k<{\sigma }_i$$

也就是说，序列里不能出现"大、小、中"这样的三元子序列（子序列不必相邻）。

两种方法怎么选：给一个序列问合不合法，用模拟法，稳；给四个选项问"哪个不可能"，先用禁用模式扫一眼锁定嫌疑，再用模拟法验证那一个，速度最快。禁用模式只用来定位嫌疑，最终结论以模拟法为准。

模拟法的逐步演示与禁用模式的三步反证（想彻底弄懂为什么就展开）

模拟法逐步演示：输入 $1,2,3$，判定 $\sigma =3,1,2$。

步	目标 ${\sigma }_t$	栈（底→顶）	动作
1	3	空	栈顶 ≠ 3，压 1
2	3	1	栈顶 1 ≠ 3，压 2
3	3	1 2	栈顶 2 ≠ 3，压 3
4	3	1 2 3	栈顶 = 3，弹出 → 输出 3
5	1	1 2	栈顶 2 ≠ 1，输入已用尽 → 不合法

所以 $3,1,2$ 不是合法出栈序列。

禁用模式的反证（三句话）：入栈顺序是 $1,2,\dots ,n$，所以值越小入栈越早。

1. ${\sigma }_j$ 和 ${\sigma }_k$ 的值都小于 ${\sigma }_i$，故两者都比 ${\sigma }_i$ 先入栈； 而 ${\sigma }_i$ 排在最前面先出栈，说明 ${\sigma }_i$ 被弹出的那一刻，${\sigma }_j$ 与 ${\sigma }_k$ 都还留在栈里、都在 ${\sigma }_i$ 的下方。
2. 又因为 ${\sigma }_j<{\sigma }_k$，${\sigma }_j$ 比 ${\sigma }_k$ 入栈更早，所以在栈中 ${\sigma }_j$ 位于 ${\sigma }_k$ 的下方。栈只能从顶上取，于是 ${\sigma }_k$ 必须先于 ${\sigma }_j$ 出栈。
3. 但序列里 ${\sigma }_j$ 排在 ${\sigma }_k$ 前面（$j<k$），即 ${\sigma }_j$ 先出栈——矛盾。

回到上面的序列：$3,1,2$ 中取 $i=1,j=2,k=3$，有 ${\sigma }_j=1<{\sigma }_k=2<{\sigma }_i=3$，命中禁用模式，不合法——与模拟法结论一致。

再看 $4,5,3,2,1$：想找"大、小、中"，从 $4$ 出发，后面是 $5,3,2,1$，其中比 $4$ 小的 $3,2,1$ 是递减的，找不出一个"小在前、中在后"的升序对；从 $5$ 出发同理。所以合法。 （验证：压 1234、弹 4、压 5、弹 5、弹 3、弹 2、弹 1。）

出栈序列：一共有多少种

$n$ 个不同元素依次入栈，合法出栈序列的总数是卡特兰数：

$$f(n)=C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{n!(n+1)!}$$

$n$	1	2	3	4	5	6
$C_n$	1	2	5	14	42	132

手算别硬套组合数，用递推 $C_n=C_{n-1}\cdot {\displaystyle \frac{2(2n-1)}{n+1}}$ 更快：$C_3=2\times \frac{2\cdot 5}{4}=5$，$C_4=5\times \frac{2\cdot 7}{5}=14$，$C_5=14\times \frac{2\cdot 9}{6}=42$。

🔴 计数只回答"总共有几个"，不回答"某个具体序列合不合法"。 遇到"下列哪个不是合法出栈序列"，卡特兰数帮不上忙，必须用模拟或禁用模式。顺带一个尺度感：$n=4$ 时合法序列共 $C_4=14$ 种，而全排列有 $4!=24$ 种，也就是有 10 种不合法。

看到 $1,2,5,14,42,132$ 这串数字就该想到卡特兰数，因为同一个数列在后面几章会反复出现——它们的组合结构其实是同一个：

计数对象	与出栈序列的对应
$n$ 个不同元素的合法出栈序列数	本篇
$n$ 对括号能组成的合法括号序列数	入栈 ↔ 左括号，出栈 ↔ 右括号；"任何前缀里出栈数不超过入栈数" ↔ "任何前缀里右括号不超过左括号"
$n$ 个结点能构成的不同形态的二叉树数目	按"左子树 $k$ 个结点、右子树 $n-1-k$ 个"分解，得到同一条递推 $f(n)=\sum f(k)f(n-1-k)$

卡特兰数递推式的推导（想会推不想背就展开）

考察最先入栈的元素 $1$ 在出栈序列中排第几。设它排第 $k$ 位（$1\le k\le n$）。 元素 $1$ 在栈底，它出栈时栈里必须只剩它自己，所以在它之前输出的 $k-1$ 个元素， 只能是编号 $2\sim k$ 这 $k-1$ 个（它们全部在 $1$ 之后入栈、之前出栈）；而编号 $k+1\sim n$ 的 $n-k$ 个元素，只能在 $1$ 出栈之后才被处理。这两段互不干扰，各自是一个规模更小的同类问题：

$$f(n)=\sum _{k=1}^{n}f(k-1)f(n-k),f(0)=1$$

这正是卡特兰数的递推式。

什么时候用栈，什么时候用队列

判据只有一句：要"最近优先"就用栈，要"先来先服务"就用队列。

应用场景	使用的数据结构	为什么是它
括号匹配	栈	嵌套结构要求"最近未匹配的左括号最先被消解"，正是 LIFO
表达式求值	栈	运算符要等到优先级更低的符号出现才结算，天然是"后压先算"
递归	栈（系统栈）	后调用的函数先返回，返回地址与局部变量的生命期呈 LIFO
迷宫求解 / 深度优先搜索	栈	走不通要退回"最近的"分岔点
层次遍历 / 广度优先搜索	队列	必须先处理完第 $k$ 层才能处理第 $k+1$ 层，先发现先处理
CPU 资源分配	队列	多进程争用 CPU，按 FIFO 排队（如时间片轮转调度）
打印缓冲区	队列	多个打印请求按提交顺序处理
设备速度匹配	队列	主机与慢速外设之间用缓冲区协调速度差异

队列在计算机系统里解决的其实是同一类问题的两面：一是主机与外设速度不匹配——CPU 远快于打印机，于是设一个打印缓冲区（本质就是队列），CPU 把任务扔进去就接着干别的，打印机按 FIFO 慢慢取；二是多用户竞争同一资源——多个进程同时要 CPU，操作系统用就绪队列管理，空闲时从队头取下一个。两者的共同点是到达顺序必须被保持、不允许插队。凡是允许插队或需要"最近优先"的场合，用的就不是队列。

考点速记

三条会被反复调用的结论：

1. 限制越多，输出序列越少：线性表 $n!$ → 栈 $C_n$ → 队列唯一 1 种。
2. 判定用模拟或禁用模式，计数用卡特兰数，两者解决的不是同一个问题。
3. 逻辑结构（栈/队列）与存储结构（顺序/链式）是两个正交的维度，上溢只属于后者。

这一节在真题里被考过的形式（题目挂在顺序栈与栈的应用几篇下）：

• 给一个出栈序列，问它可不可能，或给四个序列问"哪个不可能"——模拟法逐个跑。有的题还会加限制（比如"不允许连续三次退栈"），那就在模拟时把这条约束一并带上。
• 给一串 Push/Pop 操作，问输出序列是什么——照着操作逐步走，别自己"优化"顺序。
• 问这个出栈序列至少需要多大的栈容量——模拟一遍，记录过程中栈内元素的最大值。括号匹配题里问"容量为 3 的栈能不能处理某表达式"，问的也是同一件事：最大嵌套深度有没有超过容量。
• 出栈序列的计数——比如"以某个元素开头的序列有几个""$p_2$ 已定时 $p_3$ 有几种取值"，用卡特兰数的分解思路数，别去枚举。
• 栈的概念判断题——四个命题挑真伪，常见的错项见下面的易错。

易错："入栈次序确定，出栈次序就确定了"是错的。 恰恰相反，出栈次序有 $C_n$ 种。会这么想，多半是把"依次入栈"误解成了"全部压完再弹"。

易错："栈允许在两端操作"是错的。 那是双端队列。栈只有一个口，进出同一端。

易错："非递归重写递归程序必须使用栈"是错的。 尾递归、单向递推（如阶乘、斐波那契）都能改写成纯循环，不需要栈；只有需要保存多个待返回现场的递归（如树的遍历）才必须显式用栈。

易错：入栈序列与出栈序列可以完全相同，也可以互为倒序。 全部"压一个弹一个"就得到原序列，全部压完再全弹就得到逆序，两者都合法。

教材出处

• 栈的抽象数据类型定义（InitStack / Push / Pop / GetTop 等操作及其初始条件）： 严蔚敏《数据结构（C 语言版）》（第 2 版）p57「3.1 栈和队列的定义和特点 · ADT Stack」
• 队列的抽象数据类型定义（约定 $a_1$ 端为队头、$a_n$ 端为队尾）：同书 p69「3.5.1 队列的类型定义」
• 括号匹配与栈的"期待急迫性"解释：同书 p56「案例 3.2」
• 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图3.1 栈，p88

相关知识

顺序栈｜共享栈｜链栈（没有上溢）｜ 链式队列｜循环队列（假溢出的解决方案）｜ 双端队列（放松限制后能产生哪些序列，与出栈序列判定是同一套模拟方法）｜ 括号匹配、表达式求值、栈在递归中的应用｜ 算法的基本概念与复杂度分析

相关文章

• 顺序栈
• 共享栈
• 链栈
• 链式队列
• 循环队列
• 双端队列
• 应用：括号匹配
• 应用：表达式求值
• 应用：栈在递归中的应用
• 多维数组的存储
• 特殊矩阵的压缩存储