簡介
循環隊列就是将隊列存儲空間的最後一個位置繞到第一個位置,形成邏輯上的環狀空間,供隊列循環使用。在循環隊列結構中,當存儲空間的最後一個位置已被使用而再要進入隊運算時,隻需要存儲空間的第一個位置空閑,便可将元素加入到第一個位置,即将存儲空間的第一個位置作為隊尾。循環隊列可以更簡單防止僞溢出的發生,但隊列大小是固定的。
在循環隊列中,當隊列為空時,有front=rear,而當所有隊列空間全占滿時,也有front=rear。為了區别這兩種情況,規定循環隊列最多隻能有MaxSize-1個隊列元素,當循環隊列中隻剩下一個空存儲單元時,隊列就已經滿了。因此,隊列判空的條件是front=rear,而隊列判滿的條件是front=(rear+1)%MaxSize。
基本操作
1
// 隊列的順序存儲結構(循環隊列)
|
2
#define MAX_QSIZE 5 // 最大隊列長度+1
|
3
typedef struct {
|
4
int *base; // 初始化的動态分配存儲空間
|
5
int front; // 頭指針,若隊列不空,指向隊列頭元素
|
6
int rear; // 尾指針,若隊列不空,指向隊列尾元素的下一個位置
|
7
} SqQueue;
|
8
|
9
|
10
// 構造一個空隊列Q
|
11
SqQueue* Q_Init() {
|
12
SqQueue *Q = (SqQueue*)malloc(sizeof(SqQueue));
|
13
// 存儲分配失敗
|
14
if (!Q){
|
15
exit(OVERFLOW);
|
16
}
|
17
Q->base = (int *)malloc(MAX_QSIZE * sizeof(int));
|
18
// 存儲分配失敗
|
19
if (!Q->base){
|
20
exit(OVERFLOW);
|
21
}
|
22
Q->front = Q->rear = 0;
|
23
return Q;
|
24
}
|
25
|
26
// 銷毀隊列Q,Q不再存在
|
27
void Q_Destroy(SqQueue *Q) {
|
28
if (Q->base)
|
29
free(Q->base);
|
30
Q->base = NULL;
|
31
Q->front = Q->rear = 0;
|
32
free(Q);
|
33
}
|
34
|
35
// 将Q清為空隊列
|
36
void Q_Clear(SqQueue *Q) {
|
37
Q->front = Q->rear = 0;
|
38
}
|
39
|
40
// 若隊列Q為空隊列,則返回1;否則返回-1
|
41
int Q_Empty(SqQueue Q) {
|
42
if (Q.front == Q.rear) // 隊列空的标志
|
43
return 1;
|
44
else
|
45
return -1;
|
46
}
|
47
|
48
// 返回Q的元素個數,即隊列的長度
|
49
int Q_Length(SqQueue Q) {
|
50
return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;
|
51
}
|
52
|
53
// 若隊列不空,則用e返回Q的隊頭元素,并返回OK;否則返回ERROR
|
54
int Q_GetHead(SqQueue Q, int &e) {
|
55
if (Q.front == Q.rear) // 隊列空
|
56
return -1;
|
57
e = Q.base[Q.front];
|
58
return 1;
|
59
}
|
60
|
61
// 打印隊列中的内容
|
62
void Q_Print(SqQueue Q) {
|
63
int p = Q.front;
|
64
while (Q.rear != p) {
|
65
cout << Q.base[p] << endl;
|
66
p = (p + 1) % MAX_QSIZE;
|
67
}
|
68
}
|
69
|
70
// 插入元素e為Q的新的隊尾元素
|
71
int Q_Put(SqQueue *Q, int e) {
|
72
if ((Q->rear + 1) % MAX_QSIZE == Q->front) // 隊列滿
|
73
return -1;
|
74
Q->base[Q->rear] = e;
|
75
Q->rear = (Q->rear + 1) % MAX_QSIZE;
|
76
return 1;
|
77
}
|
78
|
79
// 若隊列不空,則删除Q的隊頭元素,用e返回其值,并返回1;否則返回-1
|
80
int Q_Poll(SqQueue *Q, int &e) {
|
81
if (Q->front == Q->rear) // 隊列空
|
82
return -1;
|
83
e = Q->base[Q->front];
|
84
Q->front = (Q->front + 1) % MAX_QSIZE;
|
85
return 1;
|
86
}
|
條件處理
循環隊列中,由于入隊時尾指針向前追趕頭指針;出隊時頭指針向前追趕尾指針,造成隊空和隊滿時頭尾指針均相等。因此,無法通過條件front==rear來判别隊列是"空"還是"滿"。
解決這個問題的方法至少有兩種:
①另設一布爾變量以區别隊列的空和滿;
②另一種方式就是數據結構常用的:隊滿時:(rear+1)%n==front,n為隊列長度(所用數組大小),由于rear,front均為所用空間的指針,循環隻是邏輯上的循環,所以需要求餘運算。如圖1所示情況,隊已滿,但是rear(5)+1=6!=front(0),對空間長度求餘,作用就在此6%6=0=front(0)。
類型定義采用環狀模型來實現隊列,各數據成員的意義如下:
front指定隊首位置,删除一個元素就将front順時針移動一位;
rear指向元素要插入的位置,插入一個元素就将rear順時針移動一位;
count存放隊列中元素的個數,當count等于MaxQSize時,不可再向隊列中插入元素。
隊列
數據結構分為線性結構和非線性結構,隊列和線性表都是線性結構。線性表是由n個數據元素組成的有限序列,該序列有惟一的“第一個”和惟一的“最後一個”數據元素;除了“第一個”和“最後一個”之外,隊列中的每個數據元素都隻有一個直接前驅和一個直接後繼。線性表的插入和删除操作可以在表中任意位置進行。隊列是一種特殊的線性表,特殊之處在于它隻允許在表的前端(front)進行删除操作,而在表的後端(rear)進行插入操作,和棧一樣,隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾,進行删除操作的端稱為隊頭。隊列中沒有元素時,稱為空隊列。
隊列的數據元素又稱為隊列元素。在隊列中插入一個隊列元素稱為入隊,從隊列中删除一個隊列元素稱為出隊。因為隊列隻允許在一端插入,在另一端删除,所以隻有最早進入隊列的元素才能最先從隊列中删除,故隊列又稱為先進先出(FIFO—first in first out)線性表。
相關詞條
相關搜索
其它詞條