队列与循环队列讲义

一、队列的基本概念

队列是一种特殊的线性表，它只允许在表的一端进行插入操作，在另一端进行删除操作。这种特性使得队列遵循先进先出（FIFO, First In First Out）的原则。

• 入队：向队列中添加元素的操作称为入队。
• 出队：从队列中移除元素的操作称为出队。
• 队头(head)：允许执行删除操作的一端。
• 队尾(tail)：允许执行插入操作的一端。

队列的实现

队列可以通过数组或链表来实现。这里我们使用数组que[N]作为示例，其中N是队列的最大容量，初始时tt=-1代表队尾指针，hh=0代表队头指针。

操作示例：

• 入队操作：将新元素加入到队尾，并更新tt指针。
• 出队操作：移除队头元素，并更新hh指针。

普通队列操作代码示例：

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 队头的值
q[hh];
// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{
}

二、循环队列

为了避免普通队列可能出现的“假溢出”问题，我们可以使用循环队列。循环队列通过将队列的存储空间视为首尾相接的环形结构来解决这个问题。

循环队列的初始化

• MAX_QUEUEU = 1000：定义循环队列的最大容量。
• 初始化时，head=tail=0。

循环队列的判断条件

• 队列为空：当head == tail时，表示队列为空。
• 队列为满：当(tail + 1) % MAX_QUEUEU == head时，表示队列已满。为了区分队列空和队列满的情况，循环队列最多只能存储MAX_QUEUEU - 1个元素。

循环队列的入队算法

1. 如果 (tail + 1) % MAX_QUEUEU == head，则表示队列已满，进行上溢处理。
2. 否则，执行tail = (tail + 1) % MAX_QUEUEU，然后将新元素赋值给que[tail]。

循环队列与普通队列对比

通过上述对比可以看出，循环队列在处理数据流时更加灵活和高效，特别适用于需要频繁进行入队和出队操作的应用场景。

循环队列代码示例

2. 循环队列
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;
// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
// 队头的值
q[hh];
// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)
{
}

循环队列解决"假满"情况，多占用一个空间

然而，循环队列引入了一个新挑战如何区分队列为空和队列为满的状？因为在这两种情况下，队头指针（front）和队尾指针（rear）都可能指向同一位置。

为解决这一判断歧义，循环队列采用浪费一个空”的策略：

队空条件：front == rear
队满条件：(rear + 1) % capacity == front

这意味着，当队尾指针的下一个位置（循环意义上）即将覆盖队头指针时，就认为队列已满，不再允许入队。因此，实际可用的存储空间为：数组总容量减-1。

例如，若分配一个大小为10的数组存储循环队列，则实际最多只能存储9个元素，第10个空间始终被保留，用于区分满与空的状态。

这种设计虽然牺牲了一个存储单元，但避免了引入额外的标志位或计数器，实现了结构简洁、判断高效，是循环队列中最经典和广泛采用的解决方案。‌

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com