线性表允许在任意位置插入和删除。当插入、删除被限制在同一端，便得到栈；当插入、删除分别被限制在两端，便得到队列。栈遵循后进先出，队列遵循先进先出；它们只暴露少量操作，却构成了函数调用、表达式求值、任务调度等大量计算过程的基础。
本章定位
本章从第 1 章的线性表出发，先分别定义栈和队列的抽象数据类型，再比较顺序存储与链式存储两种实现，最后把这两个结构放到真实问题中检验它们的价值。核心目标是建立“结构语义决定用法”的判断力：看到一个问题，能识别出它需要的是后进先出还是先进先出。
学习目标
完成本章后，你应该能够：
- 用 ADT 描述栈与队列的数据对象和基本操作，并说清各自的存取语义；
- 用顺序存储与链式存储实现栈和队列，处理空、满与非法操作等边界情况；
- 解释循环队列为什么能避免“假溢出”，并正确推导判空、判满与元素个数公式；
- 分析主要操作的时间与空间复杂度，说明扩容操作为什么是摊还
O(1)； - 用栈解决括号匹配、表达式转换与求值问题，并说明为什么队列适合广度优先的逐层扩散。
三篇文章如何分工
| 学习问题 | 对应文章 | 完成后的可检查能力 |
|---|---|---|
| 栈的结构语义和实现取舍是什么？ | 2.1 栈 | 能实现栈并分析其操作复杂度，能说明后进先出在哪些场景不可替代 |
| 队列如何避免“假溢出”，循环队列如何工作？ | 2.2 队列 | 能实现循环队列，能推导判空、判满与长度公式并设计边界测试 |
| 栈和队列能解决哪些典型问题？ | 2.3 栈与队列的应用 | 能独立完成表达式求值、单调栈与逐层扩散，并论证其复杂度 |
推荐学习顺序
- 先学习栈，建立“后进先出 + 表尾操作”的模型，再完成Lab 02-T-01：栈选择题精练检查基础概念。
- 再学习队列，重点理解循环队列判空判满的边界约定，再完成Lab 02-T-02：队列选择题精练检查公式应用与实现取舍。
- 完成基础实现练习：先做栈序列与最小栈，再做队列窗口、循环结构和用栈实现队列。
- 接着学习应用，完成其中的逆波兰表达式求值例题，并用 Lab 02-E-07 与 02-E-08 练习单调队列、单调栈与边界计算。
- 完成Lab 02-T-03：栈与队列综合理论题，用 20 道选择题和 5 道理论大题检查序列约束、结构设计与证明。
- 最后依次完成可撤销浏览器、超市收银模拟与停车场管理三个综合 Lab。
配套 Labs
| 实践主题 | 对应 Lab | 验收重点 |
|---|---|---|
| 栈的概念、边界与复杂度 | Lab 02-T-01：栈选择题精练 | 独立判断出栈序列、空满条件、括号匹配与基本操作复杂度 |
| 队列的语义、边界与实现取舍 | Lab 02-T-02：队列选择题精练 | 推导循环下标与长度，辨析链队列边界、复杂度和工程选型 |
| 栈与队列综合理论 | Lab 02-T-03：栈与队列综合理论题 | 20 道选择题与 5 道大题，完成约束分析、空间复用设计和序列计数证明 |
| 栈的模拟与接口实现 | Lab 02-E-01：验证栈序列、Lab 02-E-02：最小栈 | 从基础模拟推进到常数时间辅助状态维护 |
| 队列的窗口与接口实现 | Lab 02-E-03：最近请求、Lab 02-E-04：循环队列、Lab 02-E-05：用栈实现队列、Lab 02-E-06：循环双端队列 | 掌握滑动窗口、环绕下标、摊还分析和两端操作 |
| 单调结构进阶 | Lab 02-E-07：滑动窗口最大值、Lab 02-E-08：柱状图最大矩形、Lab 02-E-12：下一个更大元素、Lab 02-E-13：下一个更小元素、Lab 02-E-20：股票价格跨度 | 维护候选单调性，处理严格比较、相等价格和左右边界 |
| 嵌套与表达式 | Lab 02-E-09：括号匹配、Lab 02-E-10：逆波兰表达式求值、Lab 02-E-11：中缀表达式转后缀 | 区分栈顶匹配、操作数顺序、优先级与非法输入 |
| 队列与栈的进一步应用 | Lab 02-E-14：农夫抓牛、Lab 02-E-15：Josephus 出列顺序、Lab 02-E-16：二进制数生成、Lab 02-E-17：双端队列回文检查、Lab 02-E-18：反转队列前缀、Lab 02-E-19：辅助栈排序 | 练习分层搜索、循环报数、FIFO 构造、两端比较和栈队列协作 |
| 栈、导航历史与 Undo/Redo | Lab 02-P-01：可撤销浏览器 | 用完整页面状态协调后退、前进和页面级命令历史 |
| FIFO、多队列与离散时间 | Lab 02-P-02：超市收银模拟 | 统一时间口径，验证等待、逗留、忙碌率和队列峰值 |
| 栈与队列联动 | Lab 02-P-03：停车场管理 | 完成倒车、便道补位、中间删除与统计 |
Lab 编号说明
Lab 02-T-01 与 Lab 02-T-02 是交互式概念自测，Lab 02-T-03 是包含理论大题的综合训练；Lab 02-E-01 至 Lab 02-E-20 是带起始代码、参考实现和 100 分自动测试的 Program Lab；Lab 02-P-01 至 Lab 02-P-03 是综合 Project 规格，目前仍需学习者按任务说明自行创建实现。侧栏按 Theory、Exercise、Project 分类展示。
学习建议
用“语义”而非“名字”记忆
栈和队列的英文名（stack / queue）不如它们的存取语义重要：栈只在栈顶进出，队列从队尾进、队头出。做练习时，先问“这个问题的访问顺序是后进先出还是先进先出”，再决定选用哪个结构。
章节小结
栈与队列都由线性表限制操作位置得到。栈用后进先出表达“最近优先”，队列用先进先出表达“先到优先”；顺序存储与链式存储只是实现选择，不改变抽象语义。可靠实现还必须明确容量、空满条件、失败方式与复杂度前提。
章末自检
- 为什么“栈就是数组”“队列就是链表”都不准确？
- 固定容量循环队列为什么常空出一个物理槽位？
- 哪些结论是 ADT 契约，哪些结论取决于具体存储实现？
- 面对撤销、调度和逐层扩散问题时，如何从访问顺序判断应使用栈还是队列？
准备好后，从2.1 栈开始。