栈与队列的对比和选择
本节总结栈、队列和双端队列之间的区别。
学习完成后，你需要能够根据问题中的处理顺序选择合适结构：最近的先处理，通常用栈；最早的先处理，通常用队列；两端都需要灵活操作，可以考虑双端队列。
栈和队列的核心区别
Section titled “栈和队列的核心区别”栈和队列最大的区别是元素离开的顺序不同。
栈： 后进先出队列：先进先出假设元素进入顺序都是 A、B、C。
栈的离开顺序是：
C -> B -> A队列的离开顺序是：
A -> B -> C这一个差异，会直接改变整个算法或程序流程。
如何判断使用栈
Section titled “如何判断使用栈”当问题具有下面特征时，可以优先考虑栈：
- 需要处理最近出现的元素。
- 需要撤销最近一次操作。
- 需要回退到上一个状态。
- 需要匹配最近的未完成结构。
- 需要反向恢复某个过程。
典型场景包括括号匹配、函数调用、浏览器后退、编辑器撤销、表达式求值等。
栈强调的是“最近优先”。
如何判断使用队列
Section titled “如何判断使用队列”当问题具有下面特征时，可以优先考虑队列：
- 需要按照到达顺序处理。
- 先来的任务应该先执行。
- 数据需要排队等待。
- 需要一层一层扩展。
- 需要保持原始顺序。
典型场景包括打印队列、任务调度、消息缓冲、请求处理、广度优先搜索等。
队列强调的是“先来先处理”。
如何判断使用双端队列
Section titled “如何判断使用双端队列”当问题不仅需要处理一端，还需要根据情况操作两端时，可以考虑双端队列。
例如，某些滑动窗口问题中，窗口左端会随着范围移动而删除元素，右端会随着新元素加入而插入元素。还有一些问题需要同时从两端取候选值，这时双端队列会比普通栈或普通队列更合适。
双端队列强调的是“两端灵活操作”。
操作规则对比
Section titled “操作规则对比”可以用下面的方式快速记忆：
结构 插入位置 删除位置 规则栈 栈顶 栈顶 后进先出队列 队尾 队头 先进先出双端队列 两端 两端 两端可操作这张表不只是记忆用的。真正做题或设计程序时，你可以先判断数据应该从哪里进入、从哪里离开，再决定使用哪种结构。
一个常见误区是：看到线性数据就直接使用数组或列表。
实际上，如果问题的操作顺序很明确，使用栈或队列能让代码意图更清楚。比如括号匹配用普通列表也能写，但本质上是在把列表当栈使用。任务排队也可以用列表保存，但本质上是在表达队列规则。
另一个误区是：觉得双端队列功能更多，所以总是优先使用双端队列。功能更多不一定代表模型更清晰。结构选择应该服务于问题规则，而不是只看容器功能数量。
本章从受限线性表出发，学习了栈、队列、循环队列和双端队列。
栈适合处理最近优先的问题，队列适合处理先来先服务的问题，循环队列展示了队列的一种数组实现优化方式，双端队列则提供了两端都能操作的灵活模型。
选择栈还是队列，关键是看元素的处理顺序。
如果最近进入的元素应该最先离开，就使用栈。如果最早进入的元素应该最先离开，就使用队列。如果两端都需要插入和删除，就考虑双端队列。理解这些规则后，很多算法流程都会变得更容易建模。