【数据结构与算法（C语言）】循环队列图解_队列遍历过程的流程图

1. 前言

将队列的头尾相接，臆造成环状的顺序存储结构称为循环队列。

普通的顺序存储队列会出现 假溢出 情况。如下面三张图（三个步骤）描述的情况

1.1 普通循环队列假溢出

下面来看看普通队列是如何产生假溢出现象的。

1.1.1 初始化队列

此时队列为空队列。头指针和尾指针都指向第一个空间

1.1.2 插满队列

插入J1、J2、J3、J4、J5、J6，因为q->rear=6，说明队列已满

1.1.3 删除元素后，再插入元素

删除J1，J2，按道理应该是空出两个空间，可以插入新元素，但此时q ->rear指向6号地址，还是判定队列已满，如果再插入元素，q-rear=7,则队列溢出。但实际队列是有空间的

1.2 循环队列

普通的循环队列有上述假溢出缺点。于是乎，循环队列就应运而生了。

循环队列的解决假溢出方法 如下面三张图中展示的步骤：

1.2.1 插入元素，队列已满

还剩一个空间的时候，队列就满了。这样设置的原因是，如果不浪费一个空间的话，当 queue.front=queue.rear，可能会有两种情况，一个是队列为空，一个是队列已满。如果预留一个空间的话，可以用 queue.rear + 1=queue.front 判断队列已满，这样和队列为空的判断方式不冲突。

1.2.2 将元素J1、J2出列，循环队列又空出两个空间

1.2.3 元素J6可以继续入列

2. 存储结构和函数说明

2.1 队列的结构

typedef struct{
	QElemType * base;  //存储空间 
	int front;	   //队列头的下标
	int rear; 	   //队列尾的下标
}SqQueue;     //定义一个队列类型 
1
2
3
4
5

2.2 基本操作函数

和上一篇博客中的链式队列差不多，一共8个函数。

Status InitQueue(SqQueue * queue); //初始化队列
void DestroyQueue(SqQueue *queue); //销毁队列
Status ClearQueue(SqQueue * queue);//清空队列
Status QueueEmpty(SqQueue queue);  //判断队列是否为空
Status GetHead(SqQueue queue ,QElemType * e); //获取队列头元素
int QueueLength(SqQueue queue);			//获取队列长度
Status EnQueue(SqQueue  * queue, QElemType e); //元素入列
Status DeQueue(SqQueue * queue ,QElemType * e); //元素出列
1
2
3
4
5
6
7
8

2.3 初始化队列

原型：Status InitQueue(SqQueue * queue)
说明：初始化队列,申请一个头结点的内存

/*初始化队列,申请一个头结点的内存*/
Status InitQueue(SqQueue * queue)
{
	queue->base = (QElemType *) malloc(sizeof(QElemType)*MAXSIZE); //申请一个队列结点作为头结点的内存地址给 队头指针；
	if(queue->base == NULL)
		return FALSE;
	queue->front = queue->rear =0;
	return TRUE;
}

1
2
3
4
5
6
7
8
9
10

2.4 销毁队列 DestroyQueue

原型 ：void DestroyQueue(SqQueue *queue)
功能 ：销毁队列，释放队列的数据空间

/*销毁栈，释放队列的数据空间*/
void DestroyQueue(SqQueue *queue)
{
	free(queue->base);
	queue->front= queue->rear =0;
}
1
2
3
4
5
6

2.5 清空队列 ClearQueue

原型：Status ClearQueue(SqQueue * queue)
功能 ：清空队列的元素，但队列的空间保留

//将队列queue清空
Status ClearQueue(SqQueue * queue)
{
	queue->front = queue->rear = 0;
	return OK;	
}
1
2
3
4
5
6

2.6 获取队列第一个元素 GetHead

原型：Status GetHead(SqQueue queue ,QElemType * e)
功能 ：获取队列第一个元素,注意 不是删除元素

//获取队列第一个元素
Status GetHead(SqQueue queue ,QElemType * e)
{
	if(QueueEmpty(queue))
		return FALSE;
	*e=queue.base[queue.front];
	return TRUE;
}
1
2
3
4
5
6
7
8

2.7 获取队列长度

原型：int QueueLength(SqQueue queue)
功能 ：队列长度

//返回队列长度
int QueueLength(SqQueue queue)
{
	return (queue.rear - queue.front + MAXSIZE) % MAXSIZE;
}
1
2
3
4
5

2.8 元素入列 EnQueue

原型：Status EnQueue(SqQueue * queue, QElemType e)
功能 ：元素e 插入队列queue

//元素e 插入队列queue
Status EnQueue(SqQueue  * queue, QElemType e)
{
	if((queue->rear + 1) % MAXSIZE == queue->front) //队列满，
		return FALSE ;
	queue->base[queue->rear]=e;       //e 插入队列尾部，队尾加1
	queue->rear = (queue->rear + 1) % MAXSIZE;
	return TRUE;
}
1
2
3
4
5
6
7
8
9

2.9 元素出列 DeQueue

原型：Status DeQueue(SqQueue * queue ,QElemType * e)
功能 ：若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR

//若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR
Status DeQueue(SqQueue * queue ,QElemType * e)
{
	if(QueueEmpty( *queue))
		return FALSE;
	*e = queue->base[queue->front];
	queue->front= (queue->front + 1) % MAXSIZE;
	return TRUE;
}
1
2
3
4
5
6
7
8
9

2.10 遍历队列 QueueTraverse

原型：Status QueueTraverse(SqQueue queue,void (*visit)())
功能 ：遍历队列，对队列的每个元素调用Visit函数

//遍历队列，对队列的每个元素调用Visit函数
Status QueueTraverse(SqQueue queue,void (*visit)())
{
	int i = queue.front;
	if(QueueEmpty(queue))
		return FALSE ;
	if(queue.front < queue.rear)	
		while(i < queue.rear)
			visit(queue.base[i++]);
	else{
		while(i< MAXSIZE)
			visit(queue.base[i++]);
		i=0;
		while(i<queue.rear)
			visit(queue.base[i++]);
	}
	return TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3. 完整源码和测试代码

#include <stdio.h>
#include <stdlib.h>

#define TRUE  1
#define FALSE 0
#define OK    1
#define ERROR 0
#define MAXSIZE 6 //最大值设置为6

typedef  int Status;

typedef  int QElemType; //定义元素类型为整型


typedef struct{
	QElemType * base;  //存储空间 
	int front;	   //队列头的下标
	int rear; 	   //队列尾的下标
}SqQueue;     //定义一个队列类型 

Status InitQueue(SqQueue * queue);
void DestroyQueue(SqQueue *queue);
Status ClearQueue(SqQueue * queue);
Status QueueEmpty(SqQueue queue);
Status GetHead(SqQueue queue ,QElemType * e);
int QueueLength(SqQueue queue);
Status EnQueue(SqQueue  * queue, QElemType e);
Status DeQueue(SqQueue * queue ,QElemType * e);

/*初始化队列,申请一个头结点的内存*/
Status InitQueue(SqQueue * queue)
{
	queue->base = (QElemType *) malloc(sizeof(QElemType)*MAXSIZE); //申请一个队列结点作为头结点的内存地址给 队头指针；
	if(queue->base == NULL)
		return FALSE;
	queue->front = queue->rear =0;
	return TRUE;
}

/*销毁队列，释放队列的数据空间*/
void DestroyQueue(SqQueue *queue)
{
	free(queue->base);
	queue->front= queue->rear =0;
}

//将队列queue清空
Status ClearQueue(SqQueue * queue)
{
	queue->front = queue->rear = 0;
	return OK;	
}

//判断队列是否为空
Status QueueEmpty(SqQueue queue)
{
	return queue.front == queue.rear? TRUE:FALSE; 
}

//获取队列第一个元素
Status GetHead(SqQueue queue ,QElemType * e)
{
	if(QueueEmpty(queue))
		return FALSE;
	*e=queue.base[queue.front];
	return TRUE;
}


//返回队列长度
int QueueLength(SqQueue queue)
{
	return (queue.rear - queue.front + MAXSIZE) % MAXSIZE;
}


//元素e 插入队列queue
Status EnQueue(SqQueue  * queue, QElemType e)
{
	if((queue->rear + 1) % MAXSIZE == queue->front) //队列满，
		return FALSE ;
	queue->base[queue->rear]=e;       //e 插入队列尾部，队尾加1
	queue->rear = (queue->rear + 1) % MAXSIZE;
	return TRUE;
}

//若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR
Status DeQueue(SqQueue * queue ,QElemType * e)
{
	if(QueueEmpty( *queue))
		return FALSE;
	*e = queue->base[queue->front];
	queue->front= (queue->front + 1) % MAXSIZE;
	return TRUE;

}
void Visit(QElemType e)
{
	printf("%3d",e);
}
//遍历队列，对队列的每个元素调用Visit函数
Status QueueTraverse(SqQueue queue,void (*visit)())
{
	int i = queue.front;
	if(QueueEmpty(queue))
		return FALSE ;
	if(queue.front < queue.rear)	
		while(i < queue.rear)
			visit(queue.base[i++]);
	else{
		while(i< MAXSIZE)
			visit(queue.base[i++]);
		i=0;
		while(i<queue.rear)
			visit(queue.base[i++]);
	}
	return TRUE;
}

int main()
{
	QElemType e;
	SqQueue queue;
	InitQueue(&queue);
	printf("队头分别插入数字3、4、5、6、7后:");//此时队列已经满了，设置maxsize=6,实际只能存储5个，
						   //因为只剩一个空间，代表队列已满。即 front= (rear+1)%maxsize
						   //如果不留一个空间空着，那么队列满和队列空都是 front=rear,很难分辨
	EnQueue(&queue,3);
	EnQueue(&queue,4);
	EnQueue(&queue,5);
	EnQueue(&queue,6);
	EnQueue(&queue,7);
	QueueTraverse(queue,Visit);
	printf("\n继续插入数字8");
	if(EnQueue(&queue,8))
		printf("\n出问题了，队列满了，还能插入!");
	else
		printf("\n队列已满，无法插入!");
	printf("\n删除队头数字后:");
	DeQueue(&queue,&e);	    //删除后的队列中还剩4个元素
	QueueTraverse(queue,Visit);
	printf("\n继续插入8数字后：");
	EnQueue(&queue,8);	    //数字8被存放到queue.base[5]中了
	QueueTraverse(queue,Visit);
	printf("\n清空队列");
	ClearQueue(&queue);
	printf("\n队列长度:%d\n",QueueLength(queue));
	DestroyQueue(&queue);
	getchar();
	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

4. 测试结果

5. 小结

循环队列的优缺点

5.1 优点：

(a) 解决了普通的顺序存储队列的假溢出问题。
(b) 读取方便、快捷

5.2 缺点

存储空间大小固定，无法根据需要进行扩展。