队列

一、教学目标：

1、 理解队列 “先进先出（FIFO）” 核心特性及循环队列的设计初衷（解决普通队列空间浪费问题），明确两者基本操作（入队 enqueue、出队 dequeue、判空 empty、判满 full、取队首 front）；

2、 掌握基于数组的普通队列与循环队列的 C++ 自定义实现逻辑，重点突破循环队列的判空 / 判满条件、索引取模运算等核心难点；

3、 能手动模拟队列与循环队列的操作流程（如元素入队 / 出队的索引变化、空间利用情况），分析两者空间复杂度（均为 O (n)）与时间复杂度（基本操作均为 O (1)）；

4、 能识别队列适用基础场景（如任务调度、简单缓冲处理），使用自定义队列或 STL queue 容器完成基础场景代码实现，规避空队出队、满队入队等边界错误。

二、核心知识点

概述

队列（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