数据结构之循环队列详解_循环队列front和rear例题讲解

队列分为顺序队列和循环队列，顺序队列的实现有很多种方法，有数组和链表。数组实现的又分为使用队头队尾front，rear实现和利用一个变量size统计队列元素大小实现等等。并且关于size实现的顺序队列(数组和链表都实现过)我之前的数据结构文章已经实现过。

顺序队列我们可以使用排队买车票进行理解。

在讲循环队列之前，我们先讲一下顺序队列的假溢出。

1 顺序队列的假溢出

1️⃣：初始化空队列，q -> front = q -> rear = 0。

2️⃣：入队a1、a2、a3，q -> front = 0, q -> rear = 3 。

3️⃣：出队a1、a2，q -> front = 2, q -> rear = 3 。

4️⃣：入队a4、a5、a6，q -> front = 2, q -> rear = 6 。

但是执行 4️⃣ 操作后队列的"尾指针"已经超出对队列的最大范围了，之后无法再进行入队操作，而队列实际空间并未占满，就造成了假溢出。

解决上述溢出的方法

1. 将队中元素依次向队头方向移动。
2. 将队列空间设想成一个循环的表，即分配给队列的 m 个存储单元可以循环使用，当 rear 指向 MAXSIZE 时，若队列的开始端空着，又可从头使用空着的空间。当 front 为 MAXSIZE 时也是一样。

我们采用第2种方法，所以接下来第5步有：
5️⃣：入队a7，q -> front = 2, q -> rear = 0 。

2 循环队列

通过上面的解释，为了解决顺序队列的假溢出，所以我们需要引入循环队列来解决。
循环队列概念：
无论是插入还是删除，rear增加1或者front增加1，若超出所分配的空间，就让它指向这片空间的起始地址。
实现方法： 利用 模或者称为取余(mod，C语言中：%)运算。

2.1 插入元素

// 队尾入队
q -> base[q -> rear] = data;
// 更新队尾指针
q -> rear = (q -> rear + 1) % MAXSIZE;
1
2
3
4

2.2 删除元素
无论是插入还是删除，都是加1后取余。

// 队头元素出队
data = q -> base[q -> front];
// 更新队头指针
q -> front = (q -> front + 1) % MAXSIZE;
1
2
3
4

3 解决循环队列的判空、判满冲突

我们熟悉循环队列的人都知道，循环队列为空或者为满时，front都是等于rear，例如上面例子，一开始为空时，front=rear=0，当填满6个元素，rear=5+1%6=0，又变回了0。

解决方案：

• 1）另外设一个标致位以区别队空、队满。
• 2）另设一个变量，记录元素个数。
• 3）少用一个元素空间。

本文实现的方法就是第三种，但个人建议在实际使用时，更倾向使用第二种，因为它更为方便容易理解。

下图可以看到，当我们少用一个队列的空间时，当队满时必有(q->rear+1)%MAXSIZE = q->front。而为空时front=rear，这样就区分了循环队列判满和判空的情况。

3.1 循环队列常规操作

/********************* 循环队列的常规操作 **************************/

Queue    InitQueue();             	// 初始化循环队列
int      QueueFull();               // 循环队列判满
int      QueueEmpty();              // 循环队列判空
int      QueueLength();             // 求循环队列长度(元素个数)
int      EnQueue();                 // 循环队列 入队
int      DeQueue();                 // 循环队列 出队

void     QueueStatus();             // 打印队满、队空、队长状态
/****************************************************************/
1
2
3
4
5
6
7
8
9
10
11

3.2 定义循环队列结构体

#include "stdio.h"
#include "malloc.h"

#define TRUE  1
#define FALSE 0
#define MAXSIZE 10

typedef int ElemType;


// 定义循环队列结构体
typedef struct Queue {

	int *base;	// 队列首地址
	int front;	// 队列头下标
	int rear;	// 队列尾下标

}QueObj,*Queue;
//定义了结构体对象和结构体指针的形式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.3 初始化循环队列

/*
 * 初始化循环队列
*/
Queue InitQueue() {
	Queue q;
	q = malloc(sizeof(QueObj));
	// 分配循环队列空间
	q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
	q->front = q->rear = 0;
	return q;
}
1
2
3
4
5
6
7
8
9
10
11

3.4 释放循环队列

/*
* 释放队列结构体
*/
void FreeQueue(Queue q) {
	if (NULL != q) {
		if (NULL != q->base) {
			free(q->base);
			q->base = NULL;
		}
		free(q);
		q = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.5 循环队列判满
注意，循环队列判满是我们上述说的少用一个元素空间的关键，因为它预先进行了+1操作，这样就能保证当rear指向队列尾部时，若再加1取余为0，说明队列为满。例如上述，当rear=5时，由于此时还没存进元素，所以下一次插入元素时，rear=(5+1)%6==q->front，即等于0，所以此时队列为满，即6个空间存进了5个元素。
具体看下面的例子。

/*
 *  循环队列判满
 *  q 循环队列
*/
int QueueFull(Queue q) {
	if (q == NULL) {
		return FALSE;
	}
	return (q->rear + 1) % MAXSIZE == q->front;
}
1
2
3
4
5
6
7
8
9
10

3.6 循环队列判空

/*
 *  循环队列判空
 *  q 循环队列
*/
int QueueEmpty(Queue q) {
	if (q == NULL) {
		return FALSE;
	}
	return q->front == q->rear;
}
1
2
3
4
5
6
7
8
9
10

3.7 计算循环队列的长度
按照正常逻辑，计算队列长度只需要队尾减去队头即可，但是由于是循环队列，可能存在front大，rear小运算得出负数的情况，所以必须通过加上MAXSIZE再取余保证队列的大小为正数。

/*
 *  计算循环队列长度
 *  q 循环队列
*/
int QueueLength(Queue q) {
	if (q == NULL) {
		return FALSE;
	}
	return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}
1
2
3
4
5
6
7
8
9
10

3.8 循环队列入队（EnQueue）
下面可以看到，每次入队前都会判断循环队列是否为满，QueueFull与EnQueue是保证队列少一元素的关键。

/*
 *  循环队列 入队
 *  q 循环队列
 *  data 入队元素
*/
int EnQueue(Queue q, ElemType data) {
	if (QueueFull(q)) {
		return FALSE;
	}
	// 队尾入队
	q->base[q->rear] = data;
	// 更新队尾指针
	q->rear = (q->rear + 1) % MAXSIZE;
	return TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.9 循环队列出队（DeQueue）

/*
 *  循环队列 出队
 *  q 循环队列
 *  *val 用来存出队元素的数据
*/
int DeQueue(Queue q, ElemType *val) {
	if (QueueEmpty(q)) {
		return FALSE;
	}
	// 队头元素出队
	*val = q->base[q->front];
	// 更新队头指针
	q->front = (q->front + 1) % MAXSIZE;
	return TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.10 打印队满、队空、队长状态

/*
 * 打印队满、队空、队长状态
 * q 顺序队列
*/
void QueueStatus(Queue q) {
	printf("QueueFull():%d\n", QueueFull(q));
	printf("QueueEmpty():%d\n", QueueEmpty(q));
	printf("QueueLength():%d\n", QueueLength(q));
}
1
2
3
4
5
6
7
8
9

3.11 打印队列中的元素

/*
 * 打印队列中的元素
*/
void PrintQueue(Queue q) {
	if (NULL == q || NULL == q->base) {
		return;
	}
	if (QueueEmpty(q)) {
		printf("Current element of array is NULL\n");
		return;
	}
	
	//注意，由于我们判断队列满的时侯是进行+1判断的(看QueueFull函数)，所以这里必须-1打印元素
	//若不减1，则队列尾部的元素为很大的负数
	for (int i = 0; i < MAXSIZE - 1; i++) {
		printf("%d ", q->base[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4 循环队列的测试

#include "stdio.h"
#include "malloc.h"

#define TRUE  1
#define FALSE 0
#define MAXSIZE 10

typedef int ElemType;


// 定义循环队列结构体
typedef struct Queue {

	int *base;	// 队列首地址
	int front;	// 队列头下标
	int rear;	// 队列尾下标

}QueObj,*Queue;


/*
 * 初始化循环队列
*/
Queue InitQueue() {
	Queue q;
	q = malloc(sizeof(QueObj));
	// 分配循环队列空间
	q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
	q->front = q->rear = 0;
	return q;
}

/*
* 释放队列结构体
*/
void FreeQueue(Queue q) {
	if (NULL != q) {
		if (NULL != q->base) {
			free(q->base);
			q->base = NULL;
		}
		free(q);
		q = NULL;
	}
}

/*
 *  循环队列判满
 *  q 循环队列
*/
int QueueFull(Queue q) {
	if (q == NULL) {
		return FALSE;
	}
	return (q->rear + 1) % MAXSIZE == q->front;
}


/*
 *  循环队列判空
 *  q 循环队列
*/
int QueueEmpty(Queue q) {
	if (q == NULL) {
		return FALSE;
	}
	return q->front == q->rear;
}


/*
 *  计算循环队列长度
 *  q 循环队列
*/
int QueueLength(Queue q) {
	if (q == NULL) {
		return FALSE;
	}
	return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}


/*
 *  循环队列 入队
 *  q 循环队列
 *  data 入队元素
*/
int EnQueue(Queue q, ElemType data) {
	if (QueueFull(q)) {
		return FALSE;
	}
	// 队尾入队
	q->base[q->rear] = data;
	// 更新队尾指针
	q->rear = (q->rear + 1) % MAXSIZE;
	return TRUE;
}


/*
 *  循环队列 出队
 *  q 循环队列
 *  *val 用来存出队元素的数据
*/
int DeQueue(Queue q, ElemType *val) {
	if (QueueEmpty(q)) {
		return FALSE;
	}
	// 队头元素出队
	*val = q->base[q->front];
	// 更新队头指针
	q->front = (q->front + 1) % MAXSIZE;
	return TRUE;
}

/*
 * 打印队满、队空、队长状态
 * q 顺序队列
*/
void QueueStatus(Queue q) {
	printf("QueueFull():%d\n", QueueFull(q));
	printf("QueueEmpty():%d\n", QueueEmpty(q));
	printf("QueueLength():%d\n", QueueLength(q));
}


/*
 * 打印队列中的元素
*/
void PrintQueue(Queue q) {
	if (NULL == q || NULL == q->base) {
		return;
	}
	if (QueueEmpty(q)) {
		printf("Current element of array is NULL\n");
		return;
	}
	
	//注意，由于我们判断队列满的时侯是进行+1判断的(看QueueFull函数)，所以这里必须-1打印元素
	//若不减1，则队列尾部的元素为很大的负数
	for (int i = 0; i < MAXSIZE - 1; i++) {
		printf("%d ", q->base[i]);
	}
	printf("\n");
}


int main(int argc, char const *argv[])
{
	Queue q = InitQueue();
	printf("QueueMaxSize: %d\n", MAXSIZE);
	QueueStatus(q); // 打印队满、队空、队长状态
	PrintQueue(q);


	printf("\n\n");


	// 入队
	printf("EnQueue():");
	for (int i = 1; i < MAXSIZE * 2; i += 2) {
		EnQueue(q, i);
	}
	printf("\n");
	QueueStatus(q);
	PrintQueue(q);


	printf("\n\n");


	// 出队
	int val;
	printf("DeQueue():");
	while (!QueueEmpty(q)) {
		DeQueue(q, &val);
	}
	printf("\n");
	QueueStatus(q);
	PrintQueue(q);


	printf("\n\n");


	// 测试循环队列是否会假溢出
	//结果不会，因为此时rear=front=9，当执行(q->rear + 1) % MAXSIZE == q->front;会返回0
	//所以EnQueue可以往队列中插入元素返回1。然后更新rear=1，也就说rear不会由9变成10造成假溢出。
	int num = 20;
	printf("EnQueue(%d): %d\t(0 mean Failed, 1 mean Success)\n", num, EnQueue(q, num));
	QueueStatus(q);


	//释放
	FreeQueue(q);
	return 0;
}
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197

程序结果如下：

5 总结循环队列

• 1）关于循环队列的原理和实现我们已经熟悉，但是个人认为在实现循环队列时更建议使用变量区分判满和判空，优点有队列能保证有多大就存多大的元素，并且更容易理解。
• 2）而使用少一个元素空间，其关键在于判断满时预先+1取余判断，虽然可以少一个变量区分判满判空，但是不习惯的可能不易于理解。

参考文章：
C语言实现循环队列