队列与双端队列的数组实现方法模板

74 阅读 0 评论 49 点赞

我是靠谱客的博主闪闪睫毛，这篇文章主要介绍队列与双端队列的数组实现方法模板，现在分享给大家，希望可以做个参考。

队列：

一种线性数据结构，除了可以用stl中的queue，一般还可以用数组q[N]和两个变量h，t存储，分别表示队首和队尾

复制代码

1
2
3
4
5
6
7
8
9
int q[1000005];//用来模拟队列 
int h, t;//h表示对头，t表示队尾
h = 1, t = 0;//空队列的初始化
h <= t; //判断队列是否为空（非空条件）
int x; //表示需要压入队列的数字
q[++t] = x;//入队（表尾加元素） x 
h++;//出队（表头删元素） 
q[h];//查询队首（表头） 
// 时间复杂度O（1）

双端队列：

类似普通队列，只是头尾都可以添加和删除元素

复制代码

1
2
3
4
5
6
7
8
9
10
11
int q[1000005];//用来模拟队列 
int h, t;//h表示对头，t表示队尾
h = 1, t = 0;//空队列的初始化
h <= t; //判断队列是否为空（非空条件）
int x; //表示需要压入队列的数字
q[++t] = x;//表尾入队（表尾加元素） x 
t--;//表尾出队（表尾删元素）
q[--h] = x;//表头入队（表头加元素）x 
h++;//表头出队（表头删元素） 
q[h], q[t];//查询头元素，尾元素 
// 时间复杂度O（1）