前面分析順序隊的時候,我們知道,順序隊存在”假溢出”的問題,這個問題有時會造成很大的內存浪費,循環隊列就是為了解決這個問題而提出地一個很巧妙的辦法.循環隊列和順序隊列的主要區別在于:循環隊列將順序隊列臆造成一個環狀空間.在操作上這種異同體現在:
相同點:
在順序隊列和循環隊列中,進行出隊、入隊操作時,隊首、隊尾指針都要加 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));} |
運行截圖:
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
