栈与队列
本节目标
用后进先出与先进先出的访问顺序，维护嵌套结构、辅助状态和线性结构模拟。
栈和队列都只限制元素的取出顺序，却由此表达了两种很常见的时间关系。栈保留“最近还没有处理完”的状态，适合配对、嵌套、撤销与回溯；队列保留“最早到达”的元素，适合按到达顺序服务、层序遍历和事件处理。选结构前先问：下一步需要的是最近一次未完成状态，还是最早进入系统的元素？
识别信号
看到成对符号、嵌套表达式、撤销操作或“离当前位置最近的尚未匹配对象”时，优先考虑栈。栈顶正是最后压入、也最先需要完成的状态。
看到任务按到达顺序处理、请求排队或需要逐层扩展时，优先考虑队列。队首代表等待时间最长、下一步应被服务的元素。
有些题还会要求在普通栈或队列操作外查询额外信息，例如当前最小值；这时不应每次重新扫描全部元素，而要让辅助状态和主状态同步更新。
问题模型
栈保存最近未完成状态
括号匹配中，已扫描但尚未闭合的开放括号按出现顺序压栈。遇到关闭括号时，只有栈顶才可能与它匹配：更早的开放括号必须等更晚的括号先闭合。扫描结束时栈为空，才说明每个开放括号都已经配对。
队列保持到达顺序
队列把新元素放到队尾，从队首取出元素。因此每个元素的相对先后不变。若底层结构只能从一端取元素，就需要通过搬运或轮转恢复这个顺序。
主状态与辅助状态同步
最小栈把每一层保存为“当前值、压入这一层后全栈最小值”。弹出时一起删除这一层，新的栈顶已经带着正确最小值。辅助状态要逐层保存，不能只在最小值变小时更新；重复最小值弹出一个后，另一个仍需存在。
通用模板
括号匹配
遍历字符：
若是开放括号，压栈
否则栈必须非空，且栈顶必须是对应的开放括号，然后弹栈
遍历结束后，栈为空才合法
这里的不变量是：栈从底到顶依次保存已经出现、但还没有匹配关闭括号的开放括号；栈顶始终是最近一个待匹配对象。
两栈实现队列
准备输入栈和输出栈。push 只压入输入栈；pop 和 peek 需要队首时，只有输出栈为空才把输入栈全部转移到输出栈。转移会反转顺序，使最早压入的元素来到输出栈顶。
延迟搬运是关键：不要每次 push、pop 都来回搬运。一个元素从输入栈移到输出栈后，在被弹出前不会再移动，因此总搬运次数与元素数同阶，pop 与 peek 的均摊时间为 O(1)。
单队列实现栈
每次 push 后，把此前队中的所有元素依次从队首移到队尾。新元素便来到队首，队首始终代表栈顶；之后 pop 和 top 都只访问队首。代价由 push 承担，时间为 O(n)。
母题序列
按必学顺序完成下列四题；顺序从直接维护栈顶不变量，逐步迁移到同步状态和结构模拟：
- 有效的括号（必学）：识别嵌套关系，并维护最近未匹配的开放括号。
- 最小栈（必学）：让辅助最小值与每一层栈状态同步。
- 用栈实现队列（必学）：用延迟搬运把两次反转组合成先进先出。
- 用队列实现栈（必学）：用轮转不变量把后进先出放在队首。
常见误区
- 匹配关闭括号时只检查栈非空，不检查栈顶类型，错把交叉嵌套当作合法。
- 最小栈只保存一份全局最小值，弹出最小值后无法恢复先前的最小值；重复最小值尤其会暴露这个错误。
- 两栈队列每次查询都完整搬入又搬回，失去均摊
O(1)的优势。 - 单队列模拟栈后忘记轮转旧元素，队首仍是最早压入的元素，实际变成普通队列。
- 为题目保证不会发生的空
pop或空top额外设计异常协议，偏离平台接口。
迁移方向
学完本节后，单调栈会在“最近一个更大或更小元素”中继续复用栈顶的时间顺序；BFS 会把队列的到达顺序扩展为按层处理；表达式求值、浏览器撤销和调度系统则会把这里的主状态、辅助状态与延迟操作组合成更复杂的结构。遇到新题时，先明确应保留哪一种顺序，再决定是否需要额外状态或结构模拟。