队列的定义与循环队列

复习定位

队列是先进先出的线性表(FIFO)——如同排队。新数据从队尾(enqueue)进入——从队首(dequeue)离开。顺序队列使用数组实现——直接移动rear和front指针。但顺序队列的"假溢出"(尾部已满但数组前端仍然有空间)问题是线性顺序结构的问题——环数组是用取模运算将数组视为环形来解决的典型。

队列的定义和操作

队列(queue)是只允许在表的一端进行插入——另一端进行删除的线性表。插入端称为队尾(rear)——删除端称为队首(front)。

核心操作：enqueue(e)——在队尾插入元素；dequeue()——删除并返回队首元素；front()——返回队首元素不删除；isEmpty()——判断队列是否为空；size()——返回元素个数。

队列的顺序实现

简单的顺序队列使用一维数组data[MAXSIZE]——front指向队首元素下标——rear指向下一个可插入的位置(初始front=rear=0)。

入队：data[rear] = e; rear++。
出队：e = data[front]; front++。

问题——当rear增加到MAXSIZE-1时——数组尾部已没有空间——但数组前部分(下标0到front-1)仍然是空的——却无法插入——这种现象叫假溢出。如果此时继续插入——即使front>0——因为rear已到数组末尾——无法再入队——但真实可用的空闲空间还很多。

循环队列

将数组视为首尾相接的环形——指针在到达尾部时通过取模回到开头：

入队：data[rear] = e; rear = (rear + 1) % MAXSIZE
出队：e = data[front]; front = (front + 1) % MAXSIZE

判断队空：front == rear

判断队满有多种方案：

牺牲一个单元方法——(rear + 1) % MAXSIZE == front时视为队满。此时数组中有效元素最多MAXSIZE-1个——一个位置永久空闲不存放数据。这是最常用的方法——只需比较下标。

添加size变量——Queue.size记录当前元素个数——size==MAXSIZE满——size==0空。不需要牺牲单元。

设置一个标志位——bool empty_flag初始为true——入队列时置false——出队列时检查是否变空。

牺牲一个单元法最常用——判满时(rear+1)%MAXSIZE == front——判空rear==front。

链队列

用单链表实现队列——front指向第一个结点(队首)——rear指向最后一个结点(队尾)。入队——在rear后插入新结点、建立新的rear。出队——删除front指向的结点——如果队列长度为1——出队后front和rear都指向NULL。链队列没有容量限制。

队列的应用

• BFS图遍历——依靠队列的先进先出保证按层次逐层访问。
• CPU进程调度——就绪队列对所有就绪进程排队——优先享有时限的非实时调度队列的基础。
• 消息队列——生产者消费者问题中——缓冲区被抽象为队列——保证消息按发送顺序消费。
• 打印机任务队列——多个用户同时发打印任务时——先行排队的先被处理。

复习检查

1. 顺序队列的假溢出是什么意思——为什么出现——循环队列通过模除(front%M)解决问题、让指针从尾绕回头——从而利用所有已分配的空间。

2. 牺牲一个单元法(常用)的队满条件(rear+1)%M == front——如果MAXSIZE=5——rear=4,front=0——(4+1)%5==0——条件成立——队满——实际占用多少元素？为什么牺牲了哪个位置的容量？

3. 链队列(基于链表)的优点——为什么它不存在"假溢出"问题——入队只需申请新结点？

4. 循环队列的判空条件和判满条件——如果不设任何额外标志且不牺牲单元——无法区分空和满——front==rear两个状态都满足队空条件也算不满条件。去掉一个数据单元来实现状态分别的逻辑是什么。

5. 用两个栈模拟一个队列——入队push到栈1——出队如果栈2空则从栈1弹出全部元素压入栈2——再pop栈2——为什么这一操作能模拟队列的先进先出？各栈的数据元素从入队到出队经过哪些站？