手写队列分为三种,普通队列、循环队列和单调队列
其中单调队列尤为重要
普通队列
队列是一种“先进先出”的线性数据结构,依靠两个指针完成数据进出,分别为首(头)尾指针。
头指针始终指向队首元素,初始时指向队首(一般为 \(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]]; // 保存区间最小值,处理数据
}
习题
P1886 滑动窗口 /【模板】单调队列 - 洛谷
135. 最大子序和 - AcWing题库
P1434 [SHOI2002] 滑雪 - 洛谷
优先队列
详见 [[堆]]。