队列与双端队列

复习

　　栈是“后来者先走”。可很多事情恰恰相反：先来的应该先得到处理。这种“先来先服务”的顺序，对应的结构就是队列（queue）。

　　队列的规则是先进先出（FIFO，First In First Out）。

　　它就像现实中的排队：从队尾加入，从队首离开，先来的人先被服务，不会有人插队。

　　核心操作有两个：

　　它可以用链表实现（尾进头出），也可以用数组加两个指针实现（用循环的方式避免浪费前面的空间）。基本操作也都是 O(1)。

　　队列的用武之地，几乎都和“先来先服务”“缓冲”有关：

　　最后一条尤其重要——它把队列和后面的图遍历联系了起来。一个结构用在哪里，往往由它天然的顺序语义决定。

　　双端队列（deque，double-ended queue）是队列的加强版：两端都能进、都能出。

　　它同时具备栈和队列的能力：

　　所以双端队列常被当成一个“万能”的线性容器，需要哪种顺序就用哪种。当然，能力更全，实现和维护也稍复杂一点。

　　不过，队列有个隐含假设：先到的先被处理。 可如果有些任务更紧急，应该优先处理呢？那就不能只靠“先来后到”了。下一章开始，我们要给元素加上“优先级”，由此进入树与堆的世界。

思考题 1

　　队列的“先进先出”适合哪些现实场景？

思考题 2

　　双端队列与栈、队列分别是什么关系？

　　适合“先来先服务”和“缓冲”类的场景，比如打印任务、任务调度、数据缓冲区、以及广度优先搜索中的待处理节点维护。这些场景都要求按到达顺序依次处理，正好符合先进先出。

　　只用一端插入和删除时，双端队列的行为就是栈；一端插入、另一端删除时，它就是队列。所以双端队列是两者的加强版，能力更全，可以按需当作栈或队列使用。

设计师 | 南国微雪