备战蓝桥杯队列和queue详解

队列的概念

队列的静态实现

总代码

stl的queue

队列算法题

1.队列模板题

2.机器翻译

3.海港

双端队列

队列的概念

和栈一样，队列也是一种访问受限的线性表，它只能在表头位置删除，在表尾位置插入，队列是先进先出（FIFO）栈是后进先出（LIFO）

队列的静态实现

我们用一个比较大的数组来表示队列，h表示队头的前一个元素，t表示队尾元素

队列的创建

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N], h, t;

队列的插入

void push(int x)
{q[++t] = x;
}

和顺序表的尾插差不多，时间复杂度是O（1）

队列的删除

我们的删除直接让头指针向前移动一位就行了

void pop()
{h++;
}

查询队头元素

h指向的是队头的前一个元素的下标，所以h+1是队头的下标

int front()
{return q[h + 1];
}

查询队尾元素

t就是队尾元素的下标

int back()
{return q[t];
}

队列判空

当我们只剩一个元素的时候，h指向这个元素的前面，t指向这个元素，如果删除的话，h++ h就和t相等了，这和我们刚开始没有元素的状态也是一致的，所以h==t就是我们判断队列为空的要点

bool empty()
{return h == t;
}

队列有效元素个数

由于我们h和t是左开右闭的，所以t-h就是中间的元素个数，比如h指向1，t指向3的时候，下标2，3就是我们的元素，3-1=2就是元素个数是一致的

int size()
{return t - h;
}

测试

总代码

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N], h, t;
void push(int x)
{q[++t] = x;
}
void pop()
{h++;
}
int front()
{return q[h + 1];
}
int back()
{return q[t];
}
bool empty()
{return h == t;
}
int size()
{return t - h;
}
int main()
{for (int i = 1; i <= 10; i++){push(i);}while (size()){cout << front() << " " << back() << endl;pop();}return 0;
}

stl的queue

测试代码

#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
int main()
{queue <PII> q;for (int i = 1; i <= 10; i++){q.push({ i,i * 10 });}while (!q.empty()){auto t = q.front();int first = t.first;int second = t.second;cout << first << " " << second << endl;q.pop();}}

测试结果

队列算法题

1.队列模板题

#include <iostream>
using namespace std;
const int N = 1e4+10;
int q[N],h,t;int main()
{int n,op,x;cin >> n;while(n--){cin >> op;if(op == 1){cin >> x;q[++t] = x;}else if(op == 2){if(t-h == 0) cout << "ERR_CANNOT_POP" << endl;else h++;}else if(op == 3){if(t-h == 0) cout << "ERR_CANNOT_QUERY" << endl;else cout << q[h+1] << endl;}else{cout << t-h << endl;}}
}

2.机器翻译

我们可以用队列来模拟这个内存存储的单元格，此外我们还需要一个bool数组来判断某个单词在不在内存中

下面是我们的实现的代码

#include <iostream>
#include <queue>
using namespace std;
const int N = 1010;
bool st[N];
int cnt;
queue <int> q;
int main()
{int n,m;cin >> m >> n;while(n--){int x; cin >> x;if(st[x]);else{q.push(x);st[x] = true;cnt++;if(q.size() > m){st[q.front()] = false;q.pop();}}}cout << cnt << endl;
}

3.海港

这道题我们用队列来模拟，我们用一个数组来记录每个国家的人数，当每个国家从0变1时，种类加1，从1变0时，种类减1

先把每个船的信息入队列，用pair类型，<时间，国家>来入队列，每次入队列判断种类是否加1

每个船的信息入完了之后，要判断队列合不合法，如果队头的时刻和队尾的时刻差值超过24小时，我们就要把第一个时刻的信息出队列，出队列的时候再次判断要不要让种类减1

每次一个信息弄完就打印一下种类

#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5+10;
typedef pair<int,int> PII;
int t,k;
int cnt[N];//记录每个国家的人数，从0到1时种类加1，从1到0时种类减1，其他不变 
int kinds;//记录国家种类 
queue <PII> q;
int main()
{int n;cin >> n;while(n--){cin >> t >> k;while(k--){int x;cin >> x;q.push({t,x});if(cnt[x]++ == 0){kinds++;}}//让队列合法while(q.size() && (q.back().first - q.front().first >= 86400)) {int tmp;tmp = q.front().second;if(cnt[tmp]-- == 1){kinds--;}q.pop();}cout << kinds << endl;}	return 0;}

双端队列

什么是双端队列？

双端队列也是一种特殊的线性表，它允许在表的两端插入和删除元素

我们就不实现它的模拟实现了

我们直接用stl现成的双端队列deque测试一下

头插头删

#include <iostream>
#include <deque>
using namespace std;
struct node {int x, y, z;
};
deque <node> q;
int main()
{//头插和头删for (int i = 1; i <= 5; i++){q.push_front({ i,i * 5,i * 10 });}while (q.size()){auto t = q.front();q.pop_front();cout << t.x << " " << t.y << " " << t.z << endl;}
}

同理尾插和尾删

#include <iostream>
#include <deque>
using namespace std;
struct node {int x, y, z;
};
deque <node> q;
int main()
{//尾插和尾删for (int i = 1; i <= 5; i++){q.push_back({ i,i * 5,i * 10 });}while (q.size()){auto t = q.back();q.pop_back();cout << t.x << " " << t.y << " " << t.z << endl;}
}