数据结构与算法——第3章-循环队列实现入队操作(3.6.4)

发表于 分类于 ， ， 阅读时长 ≈ 3 分钟

一 概述

1
2
3
1.循环队列入队
2.循环队列出队
3.完整示例代码

二 循环队列入队

2.1 循环队列入队说明

1
2
3
循环队列实现入队操作的过程和顺序队列类似，完成以下两步操作即可：
1.将新元素添加到 rear 指向的空闲空间；
2.rear 向后移动一位，指向下一个空闲空间，为下次入队新元素做准备

2.2 循环队列入队图示

一、例如，在图 1 的基础上，向队列中添加一个新元素 5，实现过程如下图所示

图 1 图 2

说明：

1
2
3
可以看到，当顺序表还有空闲空间时，由于我们将它想象成“首尾相连”的状态， 
a[6] 和 a[0] 紧挨着，rear 变量向后移动一位，会指向 a[0] 的位置。
这意味着，队列左侧的空闲空间可以再次利用起来

二、图示3

1
2
需要注意的是，循环队列判断“已满”的方式比较特殊。
当我们根据图 2 的方法尝试将元素 6、7 分别入队时，最终的存储状态会变成下图所示

图示

说明：

1
2
3
在图 1 中，我们可以用 top==rear 作为空队列的判断标志，但图 3 中队列已满的状态也是 top==rear，明显它们
是冲突的。解决冲突常用的方法是：仍用 top==rear 作为队列为空的判断标志，将队列已满的判断方法改为
(rear+1)%MAX_LEN==top，其中 MAX_LEN 为顺序表（数组）的长度。

三、图示4

1
2
例如，在图 2 的基础尝试将元素 6 入队，此时 rear 的值为0，(rear+1)%MAX_LEN 的值为 1，而 top 的值为 2，
所以等式不成立，意味着循环队列未满，元素 6 就成功存储到了 a[0] 处。

图示

说明

1
2
3
4
5
在图 4 的基础上尝试将元素 7 入队，此时 rear 的值为 1，(rear+1)%MAX_LEN 的值为 2，而 top 的值为 2，
所以等式成立，意味着循环队列已满，元素 7 就无法入队。

有读者可能会问，图 4 的顺序表中明明还有一块空闲空间没有利用呢？是的，这就是循环队列判断“已满”的方法，
浪费一块存储空间，避免和“队列为空”的状态发生冲突

2.3 循环队列实现入队的 C 语言代码为

1
2
3
4
5
6
7
8
9
10
11
12
13
int enQueue(int* a, int top, int rear, int data) {
	//添加判断语句，如果rear超过max，则直接将其从a[0]重新开始存储，如果rear+1和top重合，则表示顺序表已满
	if ((rear + 1) % MAX_LEN == top) {
		printf("空间已满\n");
		return rear;
	}
	//将新元素入队
	a[rear % MAX_LEN] = data;
	printf("元素 %d 成功入队\n", data);
	//rear记录下一个空闲空间的位置
	rear = (rear + 1) % MAX_LEN;
	return rear;
}

说明

1
2
程序中并没有直接将 data 元素存储到 a[rear] 中，而是将其存储到 a[rear%MAX_LEN] 中，
这样就可以将顺序表当做环状表来用。

三 循环队列出队

3.1 步骤

1
2
3
循环队列实现出队的过程也和顺序队列类似，依次执行以下两步操作：
1.将 top 记录的队头元素出队；
2.将 top 向后移动一位，记录新队头元素的位置。

3.2 示例代码

前面已经讲过，循环队列判断“队列为空”的标志是 top==rear，因此循环队列实现出队操作的 C 语言代码为

1
2
3
4
5
6
7
8
9
10
11
int deQueue(int* a, int top, int rear) {
	//如果top==rear，表示队列为空
	if (top == rear) {
		printf("队列为空\n");
		return top;
	}
	printf("元素 %d 成功出队\n", a[top]);
	//top向后移动一个位置，记录新的队头
	top = (top + 1) % MAX_LEN;
	return top;
}

四 完整示例代码

为了加深读者对循环队列的认知，下面给出了 C 语言实现循环队列的完整代码，仅供参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdio.h>
#define MAX_LEN 5//表示顺序表申请的空间大小
int enQueue(int* a, int top, int rear, int data) {
	//添加判断语句，如果rear超过max，则直接将其从a[0]重新开始存储，如果rear+1和top重合，则表示顺序表已满
	if ((rear + 1) % MAX_LEN == top) {
		printf("空间已满\n");
		return rear;
	}
	//将新元素入队
	a[rear % MAX_LEN] = data;
	printf("元素 %d 成功入队\n", data);
	//rear记录下一个空闲空间的位置
	rear = (rear + 1) % MAX_LEN;
	return rear;
}
int deQueue(int* a, int top, int rear) {
	//如果top==rear，表示队列为空
	if (top == rear) {
		printf("队列为空\n");
		return top;
	}
	printf("元素 %d 成功出队\n", a[top]);
	//top向后移动一个位置，记录新的队头
	top = (top + 1) % MAX_LEN;
	return top;
}
int main() {
	/定义长度为 5 的顺序表
	int a[MAX_LEN] = {0};
	//当队列中没有元素时，队头和队尾指向同一位置
	int top = 0, rear = 0;
	//元素 1 成功入队
	rear = enQueue(a, top, rear, 1);
	//元素 2 成功入队
	rear = enQueue(a, top, rear, 2);
	//元素 3 成功入队
	rear = enQueue(a, top, rear, 3);
	//元素 4 成功入队
	rear = enQueue(a, top, rear, 4);
	//元素 5 入队会失败
	rear = enQueue(a, top, rear, 5);

	//元素 1 成功出队
	top = deQueue(a, top, rear);
	//元素 5 再入队，会成功
	rear = enQueue(a, top, rear, 5);
	//元素 2 成功出队
	top = deQueue(a, top, rear);
	//元素 3 成功出队
	top = deQueue(a, top, rear);
	//元素 4 成功出队
	top = deQueue(a, top, rear);
	//元素 5 成功出队
	top = deQueue(a, top, rear);
	//队列为空时，出队操作失败
	top = deQueue(a, top, rear);
	return 0;
}

运行结果为

1
2
3
4
5
6
7
8
9
10
11
12
元素 1 成功入队
元素 2 成功入队
元素 3 成功入队
元素 4 成功入队
空间已满
元素 1 成功出队
元素 5 成功入队
元素 2 成功出队
元素 3 成功出队
元素 4 成功出队
元素 5 成功出队
队列为空