队列 Queue

数据结构 · 先进先出的线性表

什么是队列

队列和栈一样是线性表，但它两端各管一件事：一端只进（队尾），另一端只出（队首）。就像排队买票——新来的排到队尾，叫号的总是队首那位。

从队尾加入一个元素叫 enqueue（入队），从队首拿走一个叫 dequeue（出队），只看队首而不拿走叫 peek。先排进来的先被服务——这就是先进先出（FIFO，First In First Out），正好和栈的后进先出相反。

试试连入 1、2、3，再连出两次——最先出来的是 1，谁先排队谁先走。和栈对比：同样压/入 1、2、3，栈先吐 3、队列先吐 1。enqueue 和 dequeue 都只动一端，复杂度都是 O(1)。

双端队列 Deque：两端都能进出

普通队列死守 FIFO——只能尾进头出。双端队列（deque，double-ended queue）放宽了这条限制：队头、队尾两端都能进、都能出，于是有四个操作——头部入 pushFront、尾部入 pushBack、头部出 popFront、尾部出 popBack。

正因为两端自由，它是栈和队列的共同推广：只用一端进出，就退化成栈（后进先出）；一端进、另一端出，就是普通队列（先进先出）。四个方向都点点看。

deque 的经典用途是滑动窗口最值——用一个「单调队列」在两端维护候选，进出都 O(1)；定长 deque 还能存「最近 N 条」历史 / 撤销记录，挤满了就从另一端丢掉最旧的。另外还有一种带优先级的队列——优先队列，它总让「最小/最大」的先出，本质是一个堆（见堆那篇），和这里按位置进出的 deque 是两回事。

队列在哪里用

队列天然适合「按到达顺序处理」的场景：

栈和队列是最基础的两种受限线性表。线性表家族里还有更通用的数组和链表，再往后才是有层次的非线性结构——树。