STL之队列queue（C++）

1、队列（queue）的定义

队列（queue）是一种先进先出( FIFO) 的线性表。它只允许在表尾进行插入，而在队头删除元素。
运用 queue， 必须声明请头文件：#include <queue>。
queue 声明：如声明一个元素类型为整型的 queue：queue<int> st;

2、队列（queue）的两种存储表示

（1）链队列——队列的链式表示

链队列需要头指针和尾指针才能唯一确定。空链队列的判决条件：头指针和尾指针均指向头结点，如3-11（a）所示。
注意：在删除操作中，当队列的最后一个元素被删后，队列尾指针也丢失了，因此需对尾指针重新赋值。

（2）循环队列——队列的顺序表示

对于顺序栈，初始化建空队列时，令 front = rear = 0，每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。当队列非空时，头指针时钟指向队列头元素，尾指针始终指向队列尾元素的下一个位置。
队列元素个数：( Q.rear - Q.front + MAXQSIZE ) % MAXQSIZE。
队列满的条件：( Q.rear + 1 ) % MAXQSIZE == Q.front。

3、队列（queue）的主要成员函数

（1）队列主要的四个成员函数

que.push() // 将一个元素置入queue 内。
que.front() //返回queue内的 “下一个” 元素,即队头元素。
que.back() //返回queue的最后一个元素
que.pop() //从queue中移除一个元素

（2）注意

如果queue 内没有元素，则执行 front() 和 pop() 会导致未定义的行为。所以，在使用前可以先用成员函数 size() 或 empty() 来检验容器是否为空。

（3）用法示例

#include <iostream>
#include <queue>

using namespace std;

int main(){
	queue<int> que;
	
	for(int i=0; i<10; i++){
		que.push(i); //将 i 的值依次压入队列中 
	}
	
	cout << "(1)" << que.size() << endl; // 输出队列的个数； 
	cout << "(2)" << que.front() << endl; // 访问队列的首元素
	cout << "(3)" << que.back() << endl; // 访问队列的尾元素 
	
	que.pop(); // 移除队列的首元素 
	cout << "(4)" << que.size() << endl; //移除首元素后的元素个数 
	cout << "(5)" << que.front() << endl; //移除原首元素后的“首元素” 
	
	return 0;
}

4、队列（queue）的应用

团体队列（Team Queue，UVa540）

Team Queue，UVa540

题目描述

有t个团队的人正在排一个长队。每次新来一个人时，如果他有队友在排队，那么这个新人会插队到最后一个队友的身后。如果没有任何一个队友排队，则他会排到长队的队尾。输入每个团队中所有队员的编号，要求支持如下3种指令（前两种指令可以穿插进行）。

ENQUEUEx：编号为x的人进入长队。
DEQUEUE：长队的队首出队。
STOP：停止模拟。

对于每个DEQUEUE指令，输出出队的人的编号。

输入
输入文件将包含一个或多个测试用例。每个测试用例从团队的数量开始 t (1 ≤ t ≤ 1000)。接下来是团队描述，每一个都由元素的数量组成属于团队和元素本身。元素是0范围内的整数…999999.A团队可能由多达1000个元素组成。
警告:一个测试用例可能包含多达200000(二十万)个命令，所以团队队列的实现应该是高效的:一个元素的入队和出队都应该只需要恒定的时间。

输出
对于每个测试用例，首先打印一行“场景#k”，其中k是测试用例的编号。然后，对于每个“出列”命令，在一行中打印出列的元素。打印空行在每个测试用例之后，甚至在最后一个之后。

样例输入
2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0

样例输出
Scenario #1
101
102
103
201
202
203
Scenario #2
259001
259002
259003
259004
259005
260001

问题分析

本题有两个队列：每个团队有一个队列，而团队整体又形成一个队列。例如，有3个团队1，2，3，队员集合分别为{101，102，103，104}、{201，202} 和 {301，302，303}，当前长队为 {301，303，103，101，102，201}，则3个团队的队列分别为{103，101，102}、{201}和{301，303}，团队整体的队列为{3，1，2}。

代码

#include<cstdio>
#include<queue>
#include<map>

using namespace std;

const int maxt = 1000 + 10; 

int main() {
	int t, kase = 0;
	
	while(scanf("%d", &t) == 1 && t){
		printf("Scenario #%dn", ++kase);
		
		//记录所有人的团队编号
		map<int, int> team; 	//team[x] 表示编号为 x 的人所在的团队编号
		for(int i=0; i<t; i++){
			int n, x;
			scanf("%d", &n);
			while(n--){
				scanf("%d", &x);
				team[x] = i;
			}
		} 
		
		//模拟
		queue<int> q, q2[maxt];
		for(;;){
			int x;
			char cmd[10];
			scanf("%s",cmd);
			
			if(cmd[0] == 'S') break;
			
			else if(cmd[0] == 'D'){
				int t = q.front();
				printf("%dn",q2[t].front());
				q2[t].pop();
				if(q2[t].empty()) q.pop(); //团体 t 全体出队列 
			}
			
			else if(cmd[0] == 'E'){
				scanf("%d", &x);
				int t = team[x];
				if(q2[t].empty()) q.push(t); //团队t进入队列
				q2[t].push(x); 
			}
		} 
		printf("n");
	}
	return 0;
}

最后

以上就是等待长颈鹿为你收集整理的STL之队列queue（C++）的全部内容，希望文章能够帮你解决STL之队列queue（C++）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。