前面分析顺序队的时候,我们知道,顺序队存在”假溢出”的问题,这个问题有时会造成很大的内存浪费,循环队列就是为了解决这个问题而提出地一个很巧妙的办法.循环队列和顺序队列的主要区别在于:循环队列将顺序队列臆造成一个环状空间.在操作上这种异同体现在:
相同点:
在顺序队列和循环队列中,进行出队、入队操作时,队首、队尾指针都要加 1 ,朝前移动。
不同点:
1. 在循环队列中当队首、队尾指针指向向量上界(MAX_QUEUE_SIZE-1) 时,其加1 操作的结果是指向向量的下界 0 。而在顺序队列中,说明队已满,若此时采用的是动态顺序链,可以增加申请内存.若是采用静态顺序链,只能退出程序.
2. 顺序队列中q.front = q.rear 表示队空,q.rear = MAX_QUEUE_SIZE表示队满.而在循环队列中.front=q.rear表示队空,而无法用.rear=MAX_QUEUE_SIZE表示队满.
判断循环队列队满的两种方法(本文采用第二种方法):
1.另设一个标志位以区分队列是空还是满
2.少用一个元素空间,约定以”队列头指针在队列尾指针的下一位置上”,作为队列呈满状态的标志.
第二种方法的实现:
◆ rear 所指的单元始终为空。
◆ 循环队列为空: front=rear 。
◆ 循环队列满: (rear+1)%MAX_QUEUE_SIZE=front 。
循环队列操作及指针变化情况如下图所示:
循环队列虽然可以解决”假溢出”问题,但是它不能通过动态分配的一维数组来实现,所以在实现循环队列之前,一定要为它设定一个最大队列长度.如果无法预估所需的最大队列长度,只能采用来链表实现.
代码实现:
循环队列和顺序队列的头文件是一样的
|
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
|
/* 循环队列的接口定义头文件 */
#define true 1
#define false 0
/* 队的最大长度 */
#define MAX_QUEUE_SIZE 6
/* 队列的数据类型 */
typedef int datatype;
/* 静态链的数据结构 */
typedef struct queue{
datatype sp_queue_array[MAX_QUEUE_SIZE];
/* 队头 */
int front;
/* 队尾 */
int rear;
}cir_queue;
/* 静态顺序链的接口定义 */
/* 静态链的初始化 */
cir_queue queue_init();
/* 判断队列是否为空,若为空
* 返回true
* 否则返回false
*/
int queue_empty(cir_queue q);
/* 插入元素e为队q的队尾新元素
* 插入成功返回true
* 队满返回false
*/
int queue_en(cir_queue *q, datatype e);
/* 队头元素出队
* 用e返回出队元素,并返回true
* 若队空返回false
*/
int queue_de(cir_queue *q, datatype *e);
/* 清空队 */
void queue_clear(cir_queue *q);
/* 获得队头元素
* 队列非空,用e返回队头元素,并返回true
* 否则返回false
*/
int get_front(cir_queue, datatype *e );
/* 获得队长 */
int queue_len(cir_queue q);
/* 遍历队 */
void queue_traverse(cir_queue q, void(*visit)(cir_queue q));
void visit(cir_queue s);
/* 循环队列的接口实现文件 */
#include<stdio.h>
#include<stdlib.h>
#include"cir_queue.h"
cir_queue queue_init()
{
cir_queue q;
q.front = q. rear = 0;
return q;
}
int queue_empty(cir_queue q)
{
return q.front == q.rear;
}
int queue_en(cir_queue *q, datatype e)
{
/* 判断队是否已满 */
if (q -> front == (q -> rear + 1) % MAX_QUEUE_SIZE)
return false;
/* 入队 */
q -> sp_queue_array[q -> rear] = e;
q -> rear = (q -> rear + 1) % MAX_QUEUE_SIZE;
return true;
}
int queue_de(cir_queue *q, datatype *e)
{
/* 判断队列是否为空 */
if(q -> front == q -> rear)
return false;
/* 用e返回队头元素 */
*e = q -> sp_queue_array[q -> front];
q -> front = (q -> front + 1 ) % MAX_QUEUE_SIZE;
return true;
}
void queue_clear(cir_queue *q)
{
q -> front = q -> rear = 0;
}
int get_front(cir_queue q, datatype *e)
{
/* 判断队列是否为空 */
if (q.front == q.rear)
return false;
*e = q.sp_queue_array[q.front];
return true;
}
int queue_len(cir_queue q)
{
/* 若front > rear */
if(q.front > q.rear)
return (q.rear + MAX_QUEUE_SIZE - q.front);
else
return (q.rear - q.front);
}
void queue_traverse(cir_queue q, void(*visit)(cir_queue q))
{
visit(q);
}
void visit(cir_queue q)
{
while(q.front != q.rear)
{
printf("%d ",q.sp_queue_array[q.front]);
q.front = (q.front + 1) % MAX_QUEUE_SIZE;
}
}
int main()
{
cir_queue q = queue_init();
queue_en(&q, 1);
queue_en(&q, 2);
queue_en(&q, 3);
queue_en(&q, 4);
queue_en(&q, 5);
printf("此时队长:length=%d\n", queue_len(q));
queue_traverse(q, visit);
printf("元素6再入队\n");
queue_en(&q, 6);
queue_traverse(q, visit);
datatype *x = (datatype *)malloc(sizeof(*x));
queue_de(&q,x);
printf("出队:%d,此时队长=%d\n", *x, queue_len(q));
printf("元素6再入队\n");
queue_en(&q, 6);
printf("length=%d\n", queue_len(q));
queue_traverse(q,visit);
datatype *e = (datatype *)malloc(sizeof(*e));
queue_de(&q,e);
printf("queue_de(),e=%d length=%d\n", *e, queue_len(q));
queue_traverse(q, visit);
queue_clear(&q);
queue_traverse(q, visit);
printf("length:%d\n", queue_len(q));
}
|
运行截图:
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！