线性表允许在任意位置插入和删除。当插入、删除被限制在同一端，便得到栈；当插入、删除分别被限制在两端，便得到队列。栈遵循后进先出，队列遵循先进先出；它们只暴露少量操作，却构成了函数调用、表达式求值、任务调度等大量计算过程的基础。

本章定位

本章从第 1 章的线性表出发，先分别定义栈和队列的抽象数据类型，再比较顺序存储与链式存储两种实现，最后把这两个结构放到真实问题中检验它们的价值。核心目标是建立“结构语义决定用法”的判断力：看到一个问题，能识别出它需要的是后进先出还是先进先出。

学习目标

完成本章后，你应该能够：

• 用 ADT 描述栈与队列的数据对象和基本操作，并说清各自的存取语义；
• 用顺序存储与链式存储实现栈和队列，处理空、满与非法操作等边界情况；
• 解释循环队列为什么能避免“假溢出”，并正确推导判空、判满与元素个数公式；
• 分析主要操作的时间与空间复杂度，说明扩容操作为什么是摊还 O(1)；
• 用栈解决括号匹配、表达式转换与求值问题，并说明为什么队列适合广度优先的逐层扩散。

三篇文章如何分工

学习问题	对应文章	完成后的可检查能力
栈的结构语义和实现取舍是什么？	2.1 栈	能实现栈并分析其操作复杂度，能说明后进先出在哪些场景不可替代
队列如何避免“假溢出”，循环队列如何工作？	2.2 队列	能实现循环队列，能推导判空、判满与长度公式并设计边界测试
栈和队列能解决哪些典型问题？	2.3 栈与队列的应用	能独立完成表达式求值、单调栈与逐层扩散，并论证其复杂度

推荐学习顺序

1. 先学习栈，建立“后进先出 + 表尾操作”的模型，再完成Lab 02-T-01：栈选择题精练检查基础概念。
2. 再学习队列，重点理解循环队列判空判满的边界约定，再完成Lab 02-T-02：队列选择题精练检查公式应用与实现取舍。
3. 完成基础实现练习：先做栈序列与最小栈，再做队列窗口、循环结构和用栈实现队列。
4. 接着学习应用，完成其中的逆波兰表达式求值例题，并用 Lab 02-09 与 02-10 练习单调队列、单调栈与边界计算。
5. 最后依次完成可撤销浏览器、超市收银模拟与停车场管理三个综合 Lab。

配套 Labs

实践主题	对应 Lab	验收重点
栈的概念、边界与复杂度	Lab 02-T-01：栈选择题精练	独立判断出栈序列、空满条件、括号匹配与基本操作复杂度
队列的语义、边界与实现取舍	Lab 02-T-02：队列选择题精练	推导循环下标与长度，辨析链队列边界、复杂度和工程选型
栈的模拟与接口实现	02-03 验证栈序列、02-04 最小栈	从基础模拟推进到常数时间辅助状态维护
队列的窗口与接口实现	02-05 最近请求、02-06 循环队列、02-07 用栈实现队列、02-08 循环双端队列	掌握滑动窗口、环绕下标、摊还分析和两端操作
单调结构进阶	02-09 滑动窗口最大值、02-10 柱状图最大矩形	维护候选单调性，处理窗口过期和左右边界
栈、导航历史与 Undo/Redo	Lab 02-P-01：可撤销浏览器	用完整页面状态协调后退、前进和页面级命令历史
FIFO、多队列与离散时间	Lab 02-P-02：超市收银模拟	统一时间口径，验证等待、逗留、忙碌率和队列峰值
栈与队列联动	Lab 02-P-03：停车场管理	完成倒车、便道补位、中间删除与统计

Lab 编号说明

Lab 02-01 与 Lab 02-02 是交互式概念自测；Lab 02-03 至 Lab 02-10 是带起始代码、参考实现和 100 分自动测试的 Program Lab；Lab 02-11 至 Lab 02-13 是综合 Project 规格，目前仍需学习者按任务说明自行创建实现。侧栏按 Theory、Exercise、Project 分类展示。

学习建议

用“语义”而非“名字”记忆

栈和队列的英文名（stack / queue）不如它们的存取语义重要：栈只在栈顶进出，队列从队尾进、队头出。做练习时，先问“这个问题的访问顺序是后进先出还是先进先出”，再决定选用哪个结构。

章节小结

栈与队列都由线性表限制操作位置得到。栈用后进先出表达“最近优先”，队列用先进先出表达“先到优先”；顺序存储与链式存储只是实现选择，不改变抽象语义。可靠实现还必须明确容量、空满条件、失败方式与复杂度前提。

章末自检

1. 为什么“栈就是数组”“队列就是链表”都不准确？
2. 固定容量循环队列为什么常空出一个物理槽位？
3. 哪些结论是 ADT 契约，哪些结论取决于具体存储实现？
4. 面对撤销、调度和逐层扩散问题时，如何从访问顺序判断应使用栈还是队列？

准备好后，从2.1 栈开始。