队列与双端队列：先进先出结构及其变体

如果说栈代表的是“最近进入的内容最先处理”，那么队列代表的就是另一种同样高频、但完全不同的秩序：先进先出。最早进入队列的元素，应该最先离开；后来进入的元素，则排在后面等待处理。这个规则在现实里非常自然，无论是排队买票、任务等待执行、网络请求缓冲，还是图的广度优先遍历，背后都能看到队列的影子。

和栈一样，队列也是一种对线性表访问方式做了主动限制的抽象数据类型。它并不允许你在中间任意插入、删除或随机访问，而是把操作明确分工到两端：一端负责进入，一端负责离开。也正是因为这种规则足够稳定，队列特别适合表达那些“到达顺序本身就是处理顺序”的问题。

但队列这一类结构并不只有最基础的 FIFO 队列。稍微把限制放宽一点，就会出现双端队列；如果再结合优先级，后面还会引出优先队列。也就是说，队列不是一个孤立的小知识点，而是一整类“围绕处理顺序组织数据”的结构起点。这一篇就先把最核心的两类讲清楚：普通队列，以及双端队列。

一、什么是队列

队列可以先用一句非常直观的话来理解：

队列是一种只允许在一端插入、在另一端删除的线性结构。

通常：

  • 插入的一端叫队尾；
  • 删除的一端叫队头。

于是它的核心规则就非常明确：

  • 新元素只能从队尾进入；
  • 元素离开时只能从队头出去；
  • 因此最先进入队列的元素会最先被处理。

这就是先进先出，也就是 First In First Out，常写作 FIFO。

可以把队列想成排队过闸机：

  • 新来的人只能站到队尾；
  • 真正被放行的人一定是队头那个；
  • 中间的人不能随便跳出来先走。

这类顺序非常适合描述“谁先到，谁先处理”的系统行为。

二、队列通常支持哪些操作

从 ADT 的角度看，队列最常见的操作通常有这些：

  • enqueue(x)：入队，把元素加入队尾；
  • dequeue()：出队，从队头移除元素；
  • front()：查看队头元素但不删除；
  • isEmpty()：判断队列是否为空；
  • size()：获取元素个数。

和栈一样，队列的接口也非常克制。它并不鼓励任意位置操作，而是让使用者只关心“进入顺序”和“离开顺序”。

这类接口限制看似保守，实际上非常有价值，因为它让顺序语义天然稳定下来。

三、队列为什么是线性表的另一种受限版本

如果拿队列和栈对比，会发现它们都属于“从线性表中抽象出来的受限结构”，只是限制方式不同。

1. 栈的限制
  • 只在同一端插入和删除；
  • 对应的是后进先出。
2. 队列的限制
  • 一端插入，另一端删除；
  • 对应的是先进先出。

也就是说，二者都不是自由访问的结构，而是通过限制操作方式，提炼出特定问题最需要的顺序模型。

这再次说明数据结构里一个很重要的思想：

限制操作并不一定是削弱能力，很多时候是在换取更清晰的语义和更贴切的问题表达。

四、为什么队列特别适合“到达即等待处理”的问题

因为队列的顺序规则，和很多真实系统里的处理逻辑高度一致。

例如：

  • 任务调度里，先到的任务通常先处理；
  • 打印任务会按进入打印缓冲区的顺序等待；
  • 请求进入服务端时，很多场景会按到达顺序排队；
  • 图的广度优先遍历里，先发现的节点先扩展下一层。

这些问题的共同点都是：

  • 元素需要先暂存起来；
  • 处理不是立刻发生；
  • 谁先进入等待区，谁更早轮到。

这正是队列最擅长的模式。

五、顺序队列是什么

顺序队列可以理解成：

用顺序存储结构来实现队列，通常用数组配合两个位置变量来维护队头和队尾。

最直观的想法通常是：

  • 用一个数组存元素；
  • front 指向队头位置；
  • rear 指向队尾之后的位置，或者直接指向队尾。

入队时，把新元素放到队尾方向；
出队时，让队头向后移动。

这种实现思路本身没有问题，但如果只是朴素地一直后移，会很快遇到一个典型问题：假溢出。

六、什么是假溢出，为什么会出现循环队列

假设一个顺序队列用数组实现。

  • 前面有元素不断出队；
  • 队头位置往后移动；
  • 后面再继续入队时，队尾也一直往后移。

这样一来，即使数组前半部分已经空出来了，如果实现不复用这些空间，队尾最终还是可能走到数组末端，表现得像“队列满了”。

可实际上：

  • 整个数组并没有真的装满；
  • 只是前面的空位没被重新利用。

这就是所谓的假溢出。

为了解决这个问题，就引出了循环队列。

循环队列的核心思路是：

把底层数组逻辑上首尾相连，当指针走到末端时，可以回到开头继续使用空闲位置。

这样就能更充分地利用顺序存储空间，也让顺序队列真正具备更实用的工程价值。

七、循环队列为什么这么重要

循环队列几乎是顺序队列里最值得重点掌握的版本。

因为它同时保留了两件事：

  • 数组实现的简单和高效；
  • 对空间的重复利用能力。

在循环队列中，通常会维护：

  • 队头指针；
  • 队尾指针；
  • 有时还会额外维护当前元素数量。

每次入队或出队时，指针都按“模数组长度”的方式循环前进。

这类实现特别适合：

  • 固定容量缓冲区；
  • 生产者消费者模型中的环形缓存；
  • 网络、日志、消息缓冲等连续流式处理场景。

所以循环队列虽然在教材里看起来像“顺序队列的一个优化”，但在真实系统里其实非常高频。

八、链式队列又是什么

链式队列通常是：

用链表来实现队列，并维护队头和队尾两个指针。

它的典型做法是：

  • 队头负责出队；
  • 队尾负责入队；
  • 新节点总接到尾部；
  • 出队时从头节点移除。

这种实现的好处是：

  • 不需要连续空间；
  • 不会像固定长度顺序队列那样轻易受到容量上限影响；
  • 只要维护好头尾指针，入队和出队通常都能做到 O(1)。

但链式队列也会有链表常见的代价：

  • 每个节点有额外指针开销；
  • 内存局部性通常不如数组；
  • 实现细节和边界维护比纯数组略复杂。

所以顺序队列和链式队列的差别，本质上仍然是在连续存储与链式存储之间做取舍。

九、队列的复杂度通常怎么理解

如果实现合理，队列的核心操作复杂度通常都比较稳定。

1. 入队：通常是 O(1)

无论是循环队列还是链式队列，通常都只需要改动队尾附近的状态。

2. 出队：通常是 O(1)

只需要移除队头元素并更新队头位置。

3. 查看队头：通常是 O(1)

因为队头位置本来就被维护着。

4. 判空：通常是 O(1)

因为可以通过指针关系或元素个数直接判断。

所以和栈一样，队列也是一种“规则收紧之后，核心操作复杂度很稳定”的结构。

十、为什么 BFS 几乎天然要用队列

这是队列最经典的算法应用之一。

图或树的广度优先遍历 BFS，强调的是：

  • 先访问当前层；
  • 再访问下一层；
  • 同一层里先被发现的节点，要先展开它的邻居。

这件事和队列的先进先出高度一致：

  • 新发现的节点先进入队尾等待；
  • 最早进入等待区的节点先从队头出来扩展；
  • 整个过程天然形成按层推进的顺序。

也就是说，BFS 之所以常和队列绑定，不只是因为大家约定俗成，而是因为其访问逻辑本质上就是一个先进先出的处理模型。

后面学图遍历时，你会越来越明显感受到这一点：

  • DFS 的深度回退更像栈；
  • BFS 的层次推进更像队列。

十一、双端队列是什么

双端队列，通常记作 deque，可以理解成：

允许在两端都进行插入和删除操作的线性结构。

也就是说，相比普通队列只允许“尾进头出”，双端队列把两端都开放了出来。

于是它通常支持：

  • 从队头插入；
  • 从队尾插入；
  • 从队头删除；
  • 从队尾删除。

你可以把它看成是：

  • 比普通队列更灵活；
  • 比一般线性表仍然更有顺序约束。

双端队列并不是为了“功能越多越好”，而是为了更适合某些需要两侧维护窗口、区间或状态的场景。

十二、双端队列常用在哪里

双端队列的高频应用非常多，尤其在算法和系统实现中都很实用。

1. 滑动窗口问题

例如求滑动窗口最大值、最小值，经常会用到单调双端队列。

2. 两端都可能发生状态变化的问题

比如某些缓存淘汰、区间维护、双向调度场景。

3. 既想保留队列式顺序，又需要两端灵活操作

这类情况下，双端队列通常会比普通队列更适合。

所以双端队列可以理解成“围绕队列思想做出的一个实用扩展”。

十三、双端队列和栈、队列是什么关系

这三者其实很适合放在一起比较。

1. 栈
  • 同一端进，同一端出；
  • 对应后进先出。
2. 队列
  • 一端进，另一端出；
  • 对应先进先出。
3. 双端队列
  • 两端都可以进，也都可以出；
  • 规则比普通队列更灵活。

从这个角度看，双端队列有点像是介于“严格受限结构”和“更灵活结构”之间的一种平衡方案。

十四、什么时候应该想到用队列

真正学会队列，关键还是模式识别能力。

如果一个问题具有下面这些特征，往往就应该考虑队列：

  • 元素按到达顺序等待处理；
  • 先来的状态应该先被消费；
  • 需要一边接收新元素，一边按顺序弹出旧元素；
  • 需要按层、按波次、按轮次推进；
  • 存在明显的缓冲区或排队区概念。

而如果问题还额外表现出：

  • 两端都可能发生状态变化；
  • 既要维护头部淘汰，也要维护尾部追加；
  • 需要构造某种“单调窗口”或双向维护结构；

那就可以进一步考虑双端队列。

十五、学习队列时最容易踩的坑

1. 只记住 FIFO 定义，不会识别场景

这和学栈时的问题很像。定义记住了，但题目里不容易想到。

2. 顺序队列实现时忽略假溢出问题

这会导致数组前面明明有空位，却无法继续入队。

3. 循环队列判满判空条件写错

这是实现里最常见的 bug 来源之一。

4. 只看到普通队列，不知道双端队列的价值

很多窗口类问题，如果没有双端队列视角，会很难写出高效解法。

5. 把队列和优先队列混在一起

普通队列按进入顺序处理；优先队列则按优先级处理。它们的顺序依据并不一样。

十六、为什么这一篇对后面很重要

队列看起来定义简单，但它往后连接的内容很多。

后面你会不断遇到和队列有关的主题：

  • 二叉树的层序遍历；
  • 图的 BFS；
  • 生产者消费者模型；
  • 环形缓冲区；
  • 双端队列与单调队列；
  • 优先队列与堆。

也就是说，队列并不是一个只会在基础章节里停留的结构。它和栈一样，既是具体容器，也是很多算法流程和系统调度模型的核心表达方式。

总结

队列和双端队列的重要性，不只是因为它们常见，而是因为它们把“顺序处理”和“等待消费”这类问题抽象得非常自然。真正值得先建立起来的，是这些核心认识：

  • 队列是一种一端插入、另一端删除的线性结构，核心规律是先进先出；
  • 它适合表达按到达顺序处理、按层推进和缓冲等待的问题；
  • 顺序队列实现简单，但会遇到假溢出问题，因此循环队列非常重要；
  • 链式队列不依赖连续空间，也能稳定支持 O(1) 的入队和出队；
  • 双端队列允许在两端插入和删除，是对普通队列的重要扩展；
  • 真正学会队列，不是只会 enqueue 和 dequeue，而是能识别“谁先进入等待区，谁就该先被处理”的问题模式。

把这一篇理解透之后，后面再去学字符串、树的层序遍历、图的 BFS 和优先队列时，你会越来越清楚地看到：很多看起来不同的问题，背后其实都在围绕“处理顺序”这件事展开。而队列，正是理解这类问题最基础的模型之一。

参考资源：