当前位置：首页 > news >正文

队列

news 2025/9/25 16:58:37

手写队列分为三种，普通队列、循环队列和单调队列

其中单调队列尤为重要

普通队列

队列是一种“先进先出”的线性数据结构，依靠两个指针完成数据进出，分别为首（头）尾指针。

头指针始终指向队首元素，初始时指向队首（一般为 \(0\) 下标处）。

尾指针有两种写法，一种是指向队尾元素，方便操作队尾进出与调用，另一种是指向队尾元素的下一位，方便实现循环队列，统计队列长度。

第一种

中心思想：尾指针指向队尾元素

初始化：因为最开始没有元素，所以尾指针应当指向 \(-1\) 即表示无元素（第一个元素下标为 \(0\)）。
为空判断：此时如果 \(hh \le tt\) 则说明有元素，否则队列为空
长度查询：依靠两个指针差距进行计算，即 \(\operatorname {size} = tt - hh + 1\)。（因为两个指针分别指向首尾元素）
队尾增加：使用 ++ tt 的方式，保证队尾元素和尾指针同步。

第二种

中心思想：尾指针指向队尾元素的下一位

初始化：因为队尾指针指向队尾元素的下一位，最开始没有元素，所以空元素是 \(-1\)，空元素的下一位就是 \(0\)，因此初始化队尾指针应当指向 \(0\)。
为空判断：如果头尾指针重叠，说明队列为空。（可画图思考）
长度查询：长度为 \(tt - hh\)，即比第一种的判断少一个 \(1\)（因为尾指针指向队尾元素的下一位）
队尾增加：使用 tt ++ 的方式保证 \(tt\) 始终在下一位。

无论是哪一种方式，队首弹出均为直接移动指针。

代码

// 增添
q[  ++ tt] = x / q[tt ++ ] = x  // 第一种/第二种做法// 删除
hh ++ // 两种，直接动头指针即可// 判空
if (hh <= tt) cout << "不空"; // 第一种
if (hh != tt) cout << "不空"; // 第二种// 队列长度(通过头尾指针算出)
size = tt - hh + 1  // 第一种
size = tt - hh // 第二种

习题

B3616 【模板】队列 - 洛谷
132. 小组队列 - AcWing题库
133. 蚯蚓 - AcWing题库

循环队列

普通队列一般头指针移动后，前面的空间就不在使用了，比较浪费。在已知序列最大可能长度下，我们可以使用循环队列，减少空间浪费。

      头指针   尾指针  空间极限（无法使用）V       V       v
* * * * 1 2 3 4 # # # # &^             ^ 
浪费的空间      未使用的空间

一般情况下基于第二种普通队列实现。基本思想为当指针（包括头指针和尾指针）到达数组最后一位的下一位时（即达到空间极限时），将指针直接放回队首即可。

为何？对于头指针只是指针运动，不会影响数据，因此头指针可以放心移动，而尾指针是确实影响数据的，因此要使用第二种，使尾指针“探路”。当探路的尾指针到达数组之外时，把尾指针放回队首。

代码

增添

q[tt ++ ] = x
if (tt == N) tt = 0; // N 即为数组大小，因为数组只涵盖0~N-1，// 所以一旦指针和N重合说明数据已经到达数组最后一位

弹出

hh ++ ;
if (hh == N) hh = 0; // 同理

单调队列

原理

与单调栈类似，可以维护一个单调序列，维护序列中任意一个固定长度区间内的最大/最小值（即算出一系列区间最值），时间复杂度为 \(\operatorname O(n)\)。一般尾指针指向队尾元素。

以维护严格单调递增序列为例。（对于相同元素，取下标更小的值）
大体思想为，不断把新元素与队尾元素对比，如果尾元素大于新元素，那么在队尾弹出尾元素，不断循环直到队尾元素小于新元素，加入新元素。此时的队首元素即为此区间内的最小元素。

如果下表超出了队列区间限制，进行队首弹出。

应用

可以快速得到一系列固定长度区间内的最值，从而优化时间。比如多重背包的单调队列优化，或者用于一些数据的整合（比如求出一系列区间最值，从而整合成新的数据，压缩、处理数据）。

代码

以维护严格单调递增序列为例。（对于相同元素，取下标更小的值）

int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++ )
{if (hh <= tt && q[hh] < i - m + 1) hh ++ ; // 弹出超出范围的队首// hh <= tt 是保证队列有元素，防止在空队列的情况下继续弹出// q[hh] < i - m + 1 这种写法比较直观，i - m + 1 是当前队列允许的范围的最后一位// 如果队首 q[hh] 小于这个点,就说明在范围之外,从而出列// 特别注意的是 i 不一定是当前的下标,它本身指的是当前加入队列的点的下标,这点不要搞错了while (hh <= tt && g[q[hh]] >= g[i]) tt -- ; // 正常的弹出队尾q[ ++ tt] = i;  // 加入新点if (i >= m) ans[ ++ cnt] = g[q[hh]]; // 保存区间最小值,处理数据
}