#M8013. 队列
队列
队列
队列是先进先出(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,否则返回falseq.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、填空题
队列快照是指在某一时刻队列中的元素组成的有序序列。例如,当元素1、2、3入队,元素1出队后,此刻的队列快照是"2 3"。当元素2、3也出队后,队列快照是"",即为空。现有3个正整数元素依次入队、出队。已知它们的和为8,则共有_________种可能的不同的队列快照(不同队列的相同快照只计一次)。例如,"5 2 1"、"4 2 2"、""都是可能的队列快照;而"7"不是可能的队列快照,因为剩下的2个正整数的和不可能是1。{{ input(1) }}