一、隊列的抽象數據類型描述#
類型名：隊列（Queue）
數據對象集：一個有 0 個或多個元素的有窮線性表
操作集：長度為 MaxSize 的堆棧 Q∈Queue, 隊列元素 item∈ElementType
1. 生成長度為 MaxSize 的空隊列
Queue CreatQueue(int MaxSize);
2. 判斷隊列 Q 是否已滿
bool IsFullQ(Queue Q, int MaxSize);
3. 將數據元素 item 插入隊列 Q 中
bool AddQ(Queue Q, ElementType item);
4. 判斷隊列 Q 是否已空
bool IsEmptyQ(Queue Q);
5. 刪除並返回隊首元素
ElementType DeleteQ(Queue Q);
二、隊列的順序存儲實現#
1. 定義#
隊列的順序存儲結構通常由一個一維數組和一個記錄隊列頭元素位置的變量 front以及一個記錄隊列尾元素位置的變量 rear組成。
形成的數組搬過來，變成一個環，便為循環隊列。
為了判斷隊列的空與滿，循環隊列僅使用 n-1 個數組空間
定義代碼如下
typedef struct QNode *Queue;
struct QNode {
ElementType Data[MaxSize];//一維數組
int rear;//記錄隊列尾元素位置
int front;//記錄隊列頭元素位置
int MaxSize;
//實際上front指向的是隊列頭元素下標的前一個
};
2. 操作#
(1) 創建循環隊列 (CreateQueue)#
Queue CreateQueue( int MaxSize ) {
Queue Q = (Queue)malloc(sizeof(struct QNode));
Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
Q->front = Q->rear = 0;
Q->MaxSize = MaxSize;
return Q;
}
(2) 判斷隊列是否已滿 (IsFull)#
bool IsFull( Queue PtrQ ) {//front和rear+1的取餘相等時隊列滿
return ((PtrQ->rear+1) % PtrQ->MaxSize == PtrQ->front);
}
(3) 入隊列 (AddQ)#
入隊時要判斷隊列是否已滿
bool AddQ(Queue PtrQ, ElementType item) {
if ( IsFull(PtrQ) ) {
printf("隊列滿");//front和rear+1的取餘相等時隊列滿
return false;
} else {
PtrQ->rear = (PtrQ->rear+1) % PtrQ->MaxSize;
//移動隊尾rear 以取餘運算來實現循環
PtrQ->Data[PtrQ->rear] = item;
return true;
}
}
(4) 判斷隊列是否已空 (IsEmpty)#
bool IsEmpty(Queue PtrQ) {
return ( PtrQ->front == PtrQ->rear );
}
(5) 出隊列 (DeleteQ)#
出隊時判斷當前隊列是否為空
ElementType DeleteQ(Queue PtrQ) {
if(IsEmpty(PtrQ)) {//rear和front相等時隊列空
printf("隊列空");
return false;
} else {
PtrQ->front = (PtrQ->front+1) % PtrQ->MaxSize;//移動隊首front
return PtrQ->Data[PtrQ->front];
}
}
三、隊列的鏈式存儲實現#
1. 定義#
隊列的鏈式存儲結構也可以用一個單鏈表實現，插入和刪除操作分別在鏈表的兩頭進行。隊列指針 front 應該指向鏈表頭
struct Node {
ElementType Data;
struct Node * Next;
}
struct QNode {//鏈隊列結構
struct Node *rear; //指向隊尾結點
struct Node *front; //指向隊頭結點
};
typedef struct QNode *Queue;
Queue PtrQ;
2. 操作#
(1) 不帶頭結點的鏈式隊列初始化（ CreateQueue）#
Queue CreateQueue() {
Queue Q;
Q = (Queue)malloc(sizeof(struct QNode));
Q->front = Q->rear = NULL;//兩個指針都為空
return Q;
}
(2) 不帶頭結點的鏈式隊列入隊操作#
bool AddQ(Queue PtrQ, ElementType item) {
struct Node *RearCell = PtrQ->rear;//指向隊尾元素的指針
struct Node *Temp = (struct Node *) malloc(sizeof(struct Node));
Tmp->Data = X;
Tmp->Next = NULL;
if ( PtrQ->front == NULL ) {//隊列為空 進第一個元素
PtrQ->rear = PtrQ->front = Tmp;
} else {
RearCell->Next = Tmp;
PtrQ->rear = Tmp;
}
return true;
}
(3) 不帶頭結點的鏈式隊列出隊操作#
ElementType DeleteQ(Queue PtrQ) {
struct Node * FrontCell;
ElementType FrontElem;//隊首元素的值
if (PtrQ->front == NULL) {//1.先判斷是否為空 為空無法進行出隊操作
printf("隊列空");
return ERROR;
}
FrontCell = PtrQ->front;
if(PtrQ->front == PtrQ->rear) //若隊列只有一個元素 則刪除後隊列置為空
PtrQ->front = PtrQ->rear = NULL;
else
PtrQ->front = FrontCell->Next;
FrontElem = FrontCell->Data;
free(FrontCell); //釋放被刪除結點的空間
return FrontElem;
}