知识点深化 · 数据结构 · 栈与队列
栈与队列：LIFO/FIFO 的底层与应用
栈和队列是两种受限的线性表：栈只准在一头进出（像弹夹，后压进去的先弹出），队列只准一头进另一头出（像排队买票，先来先服务）。它们看似简单，却是函数调用、括号匹配、消息队列、BFS 的底层骨架。这一页把 LIFO/FIFO 的直觉、底层实现和经典应用讲透。
① 小白第一课怎么学（4 步走，约 60 分钟）
别急着背代码，先按这四步建立直觉：
1看图建立直觉（10 分钟）
读②③：把栈想成弹夹、队列想成排队，搞懂 LIFO 和 FIFO。
2记操作与实现（15 分钟）
读④：栈的 push/pop/top，队列的 enqueue/dequeue，循环队列取模。
3手画经典题（20 分钟）
精读⑤：括号匹配、单调栈、用栈模拟队列。
4刷题纠错（15 分钟）
做⑦⑩，错题回⑥。
本课小目标学完你要能：① 说出栈和队列的进出顺序；② 用数组手写栈和循环队列；③ 解释函数调用栈、括号匹配、BFS 为什么用队列。
② 一图看懂：栈与队列全地图
读法：中心是受限线性表，上栈下队列，对比进出顺序、底层实现、经典应用与易错。
③ 本质直觉：栈是弹夹，队列是排队买票
栈（Stack）：一摞盘子，你只能从顶上放盘子、拿盘子。最后放上去的盘子最先被拿走——LIFO（Last In First Out）。操作都在栈顶：push 压入、pop 弹出、top 看一眼顶。
队列（Queue）：食堂排队，新来的排到队尾，最早到的从队头走——FIFO（First In First Out）。尾进 enqueue、头出 dequeue。
为什么需要循环队列：用数组实现普通队列时，队头出队后前面的空位用不上，队尾却到顶了——叫"假溢出"。把数组首尾相接成环，用 (tail+1)%capacity 取模，空位就能复用。
函数调用为什么是栈你在 main 里调 A，A 里调 B。执行顺序是 main→A→B，但返回顺序必须是 B 先返回、再 A、再 main——这就是 LIFO。操作系统用栈帧记录每层函数的局部变量和返回地址。
④ 完整体系与对比表
核心操作与复杂度
| 结构 | 操作 | 含义 | 复杂度 |
|---|
| 栈 | push(x) | 压入栈顶 | O(1) |
| 栈 | pop() | 弹出栈顶 | O(1) |
| 栈 | top()/peek() | 看栈顶不弹 | O(1) |
| 队列 | enqueue(x) | 队尾入队 | O(1) |
| 队列 | dequeue() | 队头出队 | O(1) |
| 双端队列 | 两端都可进出 | deque | O(1) |
数组实现循环队列
用数组 + 头指针 front + 尾指针 rear + 计数器 size。
循环队列关键公式入队：arr[rear]=x; rear=(rear+1)%cap; size++
出队：x=arr[front]; front=(front+1)%cap; size--
判空：size==0；判满：size==capacity。用 size 计数比"留一个空位"更直观，面试推荐。
经典应用
① 括号匹配
遇左括号压栈，遇右括号弹栈看是否配对；最后栈空即合法。
② 函数调用 / 递归
每层调用压栈帧，返回时弹栈——递归太深会栈溢出 StackOverflow。
③ 表达式求值
后缀表达式（逆波兰）用栈：遇数压栈，遇运算符弹两个数计算。
④ 撤销 Ctrl+Z
操作历史压栈，撤销就 pop 一步。
⑤ BFS 广度优先
用队列逐层扩展节点，保证先近后远。
⑥ 单调栈
栈内元素保持单调递增/递减，用于"找下一个更大元素"类问题 O(n)。
⑤ 用法场景与典型例题
例1（括号匹配）表达式 ( [ { } ] ) 是否合法？
左压栈右弹栈配对。
① 压 (；② 压 [；③ 压 {；④ 遇 } 弹 { 配对；⑤ 遇 ] 弹 [ 配对；⑥ 遇 ) 弹 ( 配对。栈最终空。答案：合法。
例2（用两个栈实现队列）栈 A 入、栈 B 出，怎么 enqueue/dequeue？
入队压 A，出队把 A 倒到 B。
enqueue：直接 push 到 A。dequeue：若 B 空，把 A 全部弹出压入 B（顺序就反转了），再从 B pop。B 非空就直接 pop。这样先入队的元素排在 B 顶。均摊 O(1)。
例3（循环队列）容量 4，front=2, rear=2, size=0，入队 3 个元素后 front/rear？
用 (rear+1)%4 推进。
初始空。入队①：arr[2]=a, rear=3；②：arr[3]=b, rear=(3+1)%4=0；③：arr[0]=c, rear=1。答案：front=2，rear=1，size=3。再出队就从 arr[2] 取 a。
做题心法看到"最近、最后、配对、撤销"想栈；看到"先来先服务、逐层、排队"想队列。单调栈题一律先想"栈里维护什么单调性"。
⑥ 高频错误诊断（4 条）
错误1：空栈还 pop栈空时 pop 会抛异常。务必先判空 while(!stack.isEmpty())。
错误2：循环队列假溢出数组队头出队后不回收空间，rear 到顶就报满。用取模 (rear+1)%cap 成环复用。
错误3：两个栈模拟队列时反复倒腾每次出队都把 A 倒到 B 再倒回来，白白 O(n)。正确做法：B 非空就别动，只在 B 空时一次性倒。
错误4：混淆栈和队列的顺序栈是后进先出，队列先进先出。画图时箭头方向别搞反。
⑦ 考点真题演练（4 题）
考点分布
| 考法 | 出题形式 | 应对 |
|---|
| LIFO/FIFO | 问进出顺序 | 栈后进先出，队列先进先出 |
| 循环队列 | 问 front/rear 推进 | (ptr+1)%capacity 取模 |
| 括号匹配/双栈队列 | 给过程问结果 | 左压右弹；B 空才倒 A |
| 应用识别 | 问某场景用栈还是队列 | 递归/撤销→栈；BFS/排队→队列 |
真题基础1. 栈的进出原则是？
真题中档2. 递归调用能无限进行吗？为什么会栈溢出？
真题中档3. 用数组实现循环队列时，rear 指针走到数组末尾后怎么办？
真题拔高4. 用两个栈实现队列的 dequeue，正确做法是？
⑧ 必背知识点卡
栈：LIFO 后进先出，push/pop/top 都在顶 弹夹
队列：FIFO 先进先出，尾进头出 排队
循环队列：(ptr+1)%cap 取模，size 计数判空满 防假溢出
括号匹配：左压右弹，最后栈空才合法
双栈队列：入压 A，出从 B，B 空才倒 A 均摊 O(1)
BFS：用队列逐层扩展 先近后远
单调栈：栈内保单调，求下一个更大/更小 O(n)
⑨ 应用输出：用栈实现浏览器前进/后退
场景：浏览器有后退、前进按钮，访问新网址要清空前进历史。
① 选型：后退用一个栈 backStack，前进用另一个栈 forwardStack。
② 访问新网址 A：把当前页压入 backStack，并清空 forwardStack（新访问会丢弃原前进路径）。
③ 点后退：当前页压入 forwardStack，从 backStack pop 出上一页显示。
④ 点前进：当前页压入 backStack，从 forwardStack pop 出下一页显示。
⑤ 边界：backStack 空就禁用后退；forwardStack 空就禁用前进。完美对应 LIFO。
口述思路合上书说："后退前进是两个栈，访问新页面清前进栈，后退把当前页压前进栈。"
⑩ 分层练习（基础 + 中档 + 拔高）
▍基础 6 题
基础1栈是先进先出吗？
不是，栈是后进先出 LIFO；队列才先进先出。
基础2队列的出口在哪一端？
队头（front），入口在队尾。
基础3栈的 push/pop 分别在哪端？
都在栈顶。
基础5BFS 广度优先遍历用栈还是队列？
队列，保证逐层扩展。
基础6循环队列用什么运算绕回头部？
取模 % capacity。
▍中档 6 题
中档7入栈顺序 1,2,3，哪个出栈序列不可能？
如 3,1,2：3 弹出后栈顶是 2，不可能先出 1，故 3,1,2 非法。
中档8循环队列 capacity=5，front=4，出队后 front=?
(4+1)%5=0。
中档9为什么函数递归太深会栈溢出？
每层调用都在调用栈压一个栈帧，栈大小有限（默认约 1MB），帧太多就爆。
中档10逆波兰表达式求值用什么结构？
栈：数字压栈，运算符弹两个数算完压回。
中档11双端队列 deque 能做什么？
两端都能 O(1) 进出，可实现单调队列、滑动窗口最大值。
中档12撤销操作 Ctrl+Z 为什么用栈？
操作历史后执行的要先撤销，LIFO。
▍拔高 6 题
拔高13最小栈：getMin() 要 O(1) 怎么做？
另开一个辅助栈，同步压入当前最小值；pop 时两栈一起弹。
拔高14单调栈求"下一个更大元素"原理？
栈存还没找到答案的下标，新元素更大就弹栈结算，O(n)。
拔高15循环队列为什么常少开一格或用 size？
纯靠 front==rear 分不清空和满，所以要么留一格、要么记 size。
拔高16用队列实现栈怎么做？
一个队列：入队后把前面 n-1 个元素依次重新排到队尾，队尾即栈顶。
拔高17表达式 a+b*c 后缀形式是什么？
abc*+：操作数顺序不变，运算符放两操作数之后。
拔高18消息队列为什么用 FIFO？
要保证消息按发送顺序被消费，先到的先处理。
⑪ 记忆口诀 + 7 天复习计划
三句口诀① 栈后进先出像弹夹，队列先进先出像排队。② 循环队列取模绕，front rear 加 size。③ 配对撤销用栈，BFS 排队用队列。
| 天 | 任务 | 自检 |
|---|
| 第 1 天 | 读②③④，画栈和队列进出图 | 能说出 LIFO/FIFO |
| 第 2 天 | 背操作表 + 基础 1-6 | 复杂度全对 |
| 第 3 天 | 做中档 7-12，手写循环队列入出队 | 取模算对 |
| 第 4 天 | 做拔高 13-18，推导最小栈/单调栈 | 能讲清辅助栈作用 |
| 第 5 天 | 做⑦真题 4 题 | 限时每题 2 分钟 |
| 第 6-7 天 | 合上书口述口诀，默写双栈队列 | 不看资料全默对 |
← 返回软件技术总览