queue容器

Queue是一种先进先出的数据结构，它有两个出口（类比水管的进水出水和食堂排队打饭），如下图（）：

queue模版类的定义在< queue>头文件中：

#include< queue>

1. 队列容器允许从一端（队尾）新增元素，从另一端移除元素（队头）
2. 队列中只有对头和队尾才可以被外界使用，因此队列不允许遍历
3. 队列中进数据称为–入队 push
4. 队列中出数据称为–出队 pop

定义queue对象：

queue < int>q1;
queue < double>q2;

之前在学习数据结构的队列 这节中已经阐释，这里不做过多描述，需了解更多可自行前往。

构造函数

与上篇stack容器一样分三种：

	queue<int> q1;     //默认构造函数
	queue<int> q2(q1); //拷贝构造函数
	queue<int> q3 = q1; //赋值构造函数

相关函数

push(elem);//往队尾添加元素
pop();//从队头移除第一个元素
back();//返回最后一个元素（队尾）
front();//返回第一个元素（队头）
empty();//判断队列是否为空
size();//返回队列的大小

void testQ() {
	queue<int> q1;     //默认构造函数
	q1.push(11);
	q1.push(22);
	q1.push(33);
	cout << q1.size() << endl;//打印队列大小：3
	cout << q1.front()<< endl; //打印队尾元素：11
	q1.pop(); //出队（队头元素），还剩：22，33
	cout << q1.front()<<endl;  //打印队头元素：22
	cout << q1.back() << endl; //打印队尾元素：33
	while (!q1.empty()) {
		cout << q1.front() << " "; //打印：22，33
		q1.pop();
	}
	}

练习

一堆扑克牌，里面有n张扑克牌。第一次从牌堆顶上拿出一张牌并输出，
第二次从牌堆顶上拿出一张牌把牌放回牌堆底下。重复执行直到牌堆里没牌。也就是说奇数张的牌输出，偶数张的牌放回。
先输入n代表n张牌，后输入每张纸牌的面值：
输入：4
1 2 3 4
输出：
1 3 2 4

void testQ() {
	queue<int> q1;     //默认构造函数
	int n = 0, count = 0, num = 0, flat = 1;
	cin >> n;
	count = n;
	while (count) {
		cin >> num;
		q1.push(num);
		count--;
	}
	while (!q1.empty()) {
		if (flat) {
			cout << q1.front()<<" ";
			q1.pop();
		}
		else {
			q1.push(q1.front());
			q1.pop();
		}
		flat = !flat;
	}
}

deque容器

从名称上可以看出deque应该是queue的double版本hiahia，当然在功能上不是简单的复制，下面一起来了解以下deque。
deque 双端 队列头端和尾端都可以进行插入删除操作。
deque队列为一个给定类型的元素进行线性处理，像向量一样，它能够快速随机访问任一个元素。
需要加deque头文件，当然也可以继续用queue头文件（< queue> 包含 < deque>：
std::queue 默认使用 std::deque 作为底层容器）

联系：
queue 依赖 deque（默认底层容器）
deque 不依赖 queue（是独立容器）

构造函数

deque deqT; //默认构造形式
deque a(n); // 定义一个int类型的双端队列a，并设置初始大小为n
dequea(n, elem); //构造函数将n个elem拷贝给本身
deque b(a); //拷贝构造函数,用a初始化b
deque b(beg, end); //构造函数将[ beg,end)区间中的元素拷贝给本身
//如：deque b(a.begin(), a.begin()+2); // 将a中[0,2)作为双端队列b的初始值

void testQ() {
	deque<int> q1;     //默认构造函数
	deque<int> q2(10);     //定义一个大小为10的整型双端队列
	deque<int> q3(5, 8); //定义大小为5且初始值都为8
	deque<int> q4(q1);   //使用赋值构造函数用q1初始化q4
	///将其q3中从第0个到第2个(共2个):[0,2),作为双端队列q5的初始值
	deque<int> q5(q3.begin(), q3.begin() + 2);
	cout << q5.size(); //输出：2
}

添加函数

d.push_front(const T& x);//头部添加元素
d.push_back(const T& x);//末尾添加元素
d.insert(iterator it, const T& x);//任意位置插入一个元素
d.insert(iterator it, int n, const T& x);//任意位置插入 n 个相同元素
d.insert(iterator it, iterator first, iterator last);//插入另一个向量的 [forst,last)间的数据

void testQ() { //以下队元素按队头->队尾顺序写
	deque<int> d1;     
	d1.push_front(11); //队头插入11
	d1.push_back(44);  //队尾插入44,队元素:11，44
	deque<int>::iterator it = d1.begin();
	d1.insert(it, 22); //在it(begin)位置上插入22,队元素:22,11，44
	it = d1.begin() + 2;
	d1.insert(it, 33); //在下标2的位置上插入33,队元素:22,11，33,44
	//用d1[0,2)初始化d2,d2队元素:22,11
	deque<int> d2(d1.begin(), d1.begin() + 2);
	it = d1.begin();
	//在d1队头添加d2的[0,1),d1队元素:22,22,11，33,44
	d1.insert(it,d2.begin(), d2.begin() + 1);
}

删除函数

d1.pop_front();//头部删除元素
d1.pop_back();//末尾删除元素
d1.erase(iterator it);//任意位置删除一个元素
d1.erase(iterator first, iterator last);//删除 [first,last) 之间的元素
d1.clear();//清空所有元素
接着上面的代码块：

//d1队元素:22,22,11，33,44
d1.pop_front(); //d1队元素:22,11，33,44
d1.pop_back();  //d1队元素:22,11，33
it = d1.begin() + 1;
d1.erase(it);   //d1队元素:22，33
d1.erase(d1.begin(), d1.begin() + 1);//删除[0，1),d1队元素:33
d1.clear();     //全部清空
for (int i = 0; i != d1.size(); i++)
	cout << d1[i] << " ";
cout << endl;

访问函数

下标访问：deq[1]; // 并不会检查是否越界
at 方法访问：deq.at(1);
// 以上两者的区别就是 at 会检查是否越界，是则抛出 out of range 异常（try,catch异常处理）
访问第一个元素：deq.front();
访问最后一个元素：deq.back();

若不用at，会直接报错。剩余两个访问不演示。

容量函数

d.size();//容器大小
d.max_size();//容器最大容量
d.resize();//更改容器大小
deq.empty();//容器判空

void testD() { 
	deque<int> d1;     
	for (int i = 0; i < 5; i++) {
		d1.push_back(i); 
	}
	cout<<d1.size()<<endl;         //大小为5
	cout << d1.max_size() << endl; //输出一个很大的数
	cout << d1.empty() << endl;    //判空，此时不空判为假，输出0
	d1.resize(1);              //重置大小为1
	cout << d1.size() << endl; //重置后再次输出大小：1
	d1.clear();                //清空
	cout << d1.empty() << endl; //判空,此时为空判为真，输出1
}

deq.shrink_to_fit();//减少容器大小到满足元素所占存储空间的大小

void testD() { 
	deque<int> d1;     
	for (int i = 0; i < 5; i++) {
		d1.push_back(i); 
	}
	cout<<d1.size()<<endl;         //大小为5
	d1.erase(d1.begin(), d1.begin() + 3); //删除[0,3)
	d1.shrink_to_fit();
	cout << d1.size() << endl;  //大小为2
	d1.shrink_to_fit();  //除特殊需要外可不加
	cout << d1.size() << endl;  //大小为2
}

其他函数

deq.assign(int nSize, const T& x); //多个元素赋值，类似于初始化时用数组进行赋值
swap(deque&);//交换两个同类型容器的元素

void testD() { 
	deque<int> d1;     
	d1.assign(3, 1); //d1(1,1,1)
	deque<int>d2;
	d2.assign(3, 2); //d2(2,2,2)
	d1.swap(d2);     //d1(2,2,2),d2(1,1,1)
}

练习

设计一个排队程序，用户有普通客人和 VIP 客人之分，VIP 客人不排队（即 VIP 客人在队列头部），请将已有的guest1和guest2放入队列中（guest1排在guest2前），并将VIP客人新增至队列头部。
输入描述：
无
输出描述：
VIP客人姓名 guest1姓名 guest2姓名（每个客人的名字用空格隔开）

void testD() { 
	Guest guest1("大明", false);
	Guest guest2("李华", false);
	Guest guest3("萨姆", true);
	deque<Guest> g;     
	g.push_back(guest1);
	g.push_back(guest2);
	g.push_front(guest3);
	for (auto i = 0; i != 3; i++) {
		cout << g[i].name << " ";   //输出：萨姆，大明，李华
	}
}