数据结构--队列
本文写于 2020 年 3 月 21 日,2022 年 3 月 6 日重新整理
写在前面
队列 (Queue)
也是线性表中的一种重要数据结构,队列中的元素只能在队列的头部 (front)
出队 (delete)
,只能在队列的尾部 (rear)
入队 (add)
。因此它是一种先入先出 (First In First Out)
的数据结构。
定义
操作集
一个队列应有以下操作:
1 | Queue *createQueue(); //生成队列 |
实现
链式结构
链式结构的队列由两个节点域组成,它们分别是 front
和 rear
节点,指向链表头和链表尾。
0. 原型
1 | typedef struct queueNode |
1. 生成空队列
生成一个 Queue
结构体,并把它的 front
和 rear
节点赋值为 NULL
。
1 | Queue *createQueue() |
2. 查询是否为满队列
链式实现的队列不存在满队列
3. 查询是否为空队列
当且仅当链式实现的队列为空队列时,它的头节点 front
为 NULL
。
1 | int isEmpty(Queue *queue) |
4. 入队
入队时,若队列不为空把尾节点的 next
节点赋值为要入队的节点,然后把尾节点移动到新插入的节点,否则,把头节点赋值为新插入的节点。
1 | void add(Queue *queue, ElementType item) |
5. 出队
出队时,若队列不为空,先把头节点保存下来,然后把头节点后移,最后删除并返回原头节点。
1 | ElementType delete (Queue *queue) |
顺序结构
0. 原型
顺序结构的队列使用一个数组存放数据,它的内部维护两个整形变量 front
和 rear
分别指示队列头部和尾部节点的位置。
由于队列的入队和出队的操作将改变队列元素在内部数组中的起始和终止位置,因此顺序结构的队列常常是一个循环队列,即内部数组循环使用,数组下标对数组长度取模,这样可以提高空间的利用效率。
容易知道,当队列的 front
和 rear
值相同时,队列是空的,同时,当队列处于满的状态时, front
和 rear
也是相同的,这种情况将使我们无法分辨队列的满空状态。
这种情况的出现是必然的,比如对于一个长度为 10
的队列,它的内部可以有 0,1,2,3...10
个元素,即 11
个状态,我们使用头尾差值即 front - rear
的值表征这 11
中状态。然而 front - rear
只有 10
种可能的结果,无法表征 11
种状态。
这种矛盾的解决方案十分简单,我们可以在队列的内部增加一个 counter
计数器来记录队列内部的元素个数。或者我们可以让头节点 front
指向队列中第一个元素的前一位置,这样,队列内部实际只能储存数组长度减一个元素,头尾节点便不会因为队列满而相遇了。
1 | typedef struct queue_array_based |
1. 生成队列
生成最大长度为 maxSize - 1
的队列,并把 front
,rear
赋值为 0
,标志为空队列。
1 | Queue *createQueue(const int maxSize) |
2. 查询队列是否为满队列
当且仅当队列满时, rear
和 front
必定是相邻位置,且 rear
在 front
后面,因此,通过判断 front + 1
与数组长度的余与 rear
比较,可以获知队列是否已满。
1 | int isFull(Queue *queue, const int maxSize) |
3. 查询队列是否为空
当且仅当队列空时, front
和 rear
的值相等。
1 | int isEmpty(Queue *queue) |
4. 入队
入队时,若队列未满, rear
的值变为 rear + 1
对数组长度的取余,然后把入对的元素放在 rear
的位置。
1 | void add(Queue *queue, ElementType item, const int maxSize) |
5. 出队
出队时,若队列非空,将 front
移到 front + 1
对数组长度取余的位置,然后返回 front
位置的元素。
1 | ElementType delete (Queue *queue, const int maxSize) |