队列

队列是先进先出（FIFO，First-In-First-Out）的线性表。队列只允许在后端（称为back，rear，tail）进行插入操作，在前端（称为front，head）进行删除操作。

队列的操作

入队：在队尾（称为back）进行插入或添加操作；

出队：在队头（称为front）进行删除操作。

数组模拟队列

int q[SIZE], front = 1, back = 0;	//定义队列q，队头与队尾
q[++back] = x;			//队尾插入元素
front++;				//队头删除元素
cout << q[front];		//访问队头
cout << q[back];		//访问队尾
front = 1, back = 0;	//清空队列

STL中的队列

STL 中的 queue 容器提供了一众成员函数以供调用。其中较为常用的有：

• 元素访问
  • q.front() 返回队首元素
  • q.back() 返回队尾元素
• 修改
  • q.push() 在队尾插入元素
  • q.pop() 弹出队首元素
• 容量
  • q.empty() 队列是否为空，若为空则返回true，否则返回false
  • q.size() 返回队列中元素的数量

此外，queue 还提供了一些运算符。较为常用的是使用赋值运算符 = 为 queue 赋值，示例：

#include<queue>						//使用queue需要对应的头文件
queue<int> q1, q2;					//新建两个队列q1,q2
q1.push(1);							//q1入队1
q2 = q1;							//queue可以进行整体赋值，将q1赋值给q2
cout << q1.front();					//输出q1队头，仅有一个元素1，输出为1
cout << q2.back();					//输出q2队尾，仅有一个元素1，输出为1
q1.pop();							//q1出队
if(!q2.empty) cout << q2.size();	//如果q2不为空，输出q2元素数量，仅有一个元素，输出为1

填空题

队列快照是指在某一时刻队列中的元素组成的有序序列。例如，当元素1、2、3入队，元素1出队后，此刻的队列快照是"2 3"。当元素2、3也出队后，队列快照是""，即为空。现有3个正整数元素依次入队、出队。已知它们的和为8，则共有_________种可能的不同的队列快照（不同队列的相同快照只计一次）。例如，"5 2 1"、"4 2 2"、""都是可能的队列快照；而"7"不是可能的队列快照，因为剩下的2个正整数的和不可能是1。