队列

概述

队列（queue）是一种具有「先进入队列的元素一定先出队列」性质的表。由于该性质，队列通常也被称为先进先出（first in first out）表，简称 FIFO 表。

实现方式有两种：

• 数组模拟队列
• STL 的 queue

数组模拟队列

首先根据数据范围定义一个数组，以最基础的数据类型都为 int 为例，例如 int q[N];

使用两个变量标记队列的头部和尾部，通常使用 int h = 1, t = 0; 设置为 $1$ 和 $0$ 表明当 $h>t$ 说明队列里还没有元素。

• 插入元素：q[++t] = x; 加入元素移动队尾这个变量。
• 删除队头元素：h++;
• 访问队首：cout << q[h];
• 访问队尾：cout << q[t];
• 清空队列：h = 1, t = 0;，当 $j=1,t=0$ 回到初始状态，队列为空。
• 队列元素个数：cout << t - h + 1;

STL 的 queue

使用方法为 queue<元素类型> 队列名字，使用前需要先引入 <queue> 头文件或万能头文件。例如 queue<int> q;

• 插入元素：q.push(x)。元素加入到队尾。
• 删除队头元素：q.pop(); 注意保证队列不为空在使用。
• 访问队首：cout << q.front(); 注意保证队列不为空在使用。
• 访问队尾：cout << q.back(); 注意保证队列不为空在使用。
• 清空队列：使用 while 循环遍历队列，进行 pop() 操作。例如：while (q.size()) q.pop();
• 队列元素个数：cout << q.size();
• 队列是否为空：cout << q.empty(); 为空返回 true 否则返回 false