文章目錄 - 順序隊列正常操作
- 定義順序隊列結構體
- 初始化順序隊列
- 順序隊列判滿
- 順序隊列判空
- 計算順序隊列的長度
- 順序隊列入隊（EnQueue）
- 順序隊列出隊（DeQueue）
- 順序隊列各操作測試
- 源代碼
順序隊列正常操作
/********************* 順序隊列的正常操作 *************************/
Queue InitSeQueue(); // 初始化順序隊列
int QueueFull(); // 判斷順序隊列滿
int QueueEmpty(); // 判斷順序隊列空
int QueueLength(); // 求順序隊列長度(元素個數)
int EnQueue(); // 入隊
int DeQueue(); // 出隊
/****************************************************************/ 複制
定義順序隊列結構體
#include "stdio.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define MAXSIZE 10 // 隊列最大的存儲量
typedef int ElemType;
// 定義順序隊列結構體
typedef struct SeQueue{
ElemType *base; // 隊列首位址
int front; // 隊列頭下标
int rear; // 隊列尾下标
}*Queue; 複制
順序隊列和順序棧相類似，在隊列的順序存儲結構中，除了用一組位址連續的存儲單元依次存放從隊列頭到隊列尾的元素之外，尚需附設兩個 “指針”
front
和
rear
分别訓示隊列頭元素及隊列尾元素的位置。
為了在C語言中描述友善起見，初始化建空隊列時，令
front = rear = 0;
每當插入新的隊尾元素時 “尾指針增1”；每當删除隊頭元素時 “頭指針增1”。
是以，在非空隊列中，頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾元素的下一個位置。
初始化順序隊列
/*
* 初始化順序隊列
*/
Queue InitSeQueue(){
Queue q;
// 配置設定隊列空間
q -> base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
q -> front = q -> rear = 0; // 開始隊列的頭尾下标相等
return q;
} 複制
順序隊列判滿
/*
* 順序隊列判滿
* q 順序隊列
*/
int QueueFull(Queue q){
if(q == NULL){
return FALSE;
}
// 判斷隊列尾下标是否超過最大容量
if(q -> rear >= MAXSIZE){
return TRUE;
}
return FALSE;
} 複制
順序隊列判空
/*
* 順序隊列判空
* q 順序隊列
*/
int QueueEmpty(Queue q){
if(q == NULL){
return FALSE;
}
return q -> front == q -> rear;
} 複制
計算順序隊列的長度
/*
* 求順序隊列的長度(元素個數)
* q 順序隊列
*/
int QueueLength(Queue q){
if(q == NULL){
return FALSE;
}
return q -> rear - q -> front;
} 複制
順序隊列入隊（EnQueue）
/*
* 入隊
* q 順序隊列
* data 入隊元素
*/
int EnQueue(Queue q, ElemType data){
// 隊列判滿
if(QueueFull(q)){
return FALSE;
}
// 把元素插入隊尾
q -> base[q -> rear] = data;
q -> rear++;
return TRUE;
} 複制
順序隊列出隊（DeQueue）
/*
* 出隊
* q 順序隊列
* *val 用來存出隊元素的資料
*/
int DeQueue(Queue q, ElemType *val){
// 隊列判空
if(QueueEmpty(q)){
return FALSE;
}
// 把隊頭元素取出來并利用指針傳回去
*val = q -> base[q -> front];
q -> front ++;
return TRUE;
} 複制
順序隊列各操作測試
/*
* 列印隊滿、隊空、隊長狀态
* q 順序隊列
*/
void QueueStatus(Queue q){
printf("QueueFull():%d\n", QueueFull(q));
printf("QueueEmpty():%d\n", QueueEmpty(q));
printf("QueueLength():%d\n\n", QueueLength(q));
}
// 程式主入口
int main(int argc, char const *argv[])
{
Queue q = InitSeQueue();
printf("QueueMaxSize: %d\n\n", MAXSIZE);
QueueStatus(q); // 列印隊滿、隊空、隊長狀态
// 入隊
printf("EnQueue():");
for(int i = 1; i < MAXSIZE * 2; i+=2){
printf("%d\t", i);
EnQueue(q, i);
}
printf("\n");
QueueStatus(q);
// 出隊
int val;
printf("DeQueue():");
while(!QueueEmpty(q)){
DeQueue(q, &val);
printf("%d\t", val);
}
printf("\n");
QueueStatus(q);
// 此時隊列元素全出隊了，測試假溢出
int num = 20;
printf("EnQueue(%d): %d\t(0 Failed, 1 Success)\n", num, EnQueue(q, num));
return 0;
} 複制
結果如下：
QueueMaxSize: 10
QueueFull():0
QueueEmpty():1
QueueLength():0
EnQueue():1 3 5 7 9 11 13 15 17 19
QueueFull():1
QueueEmpty():0
QueueLength():10
DeQueue():1 3 5 7 9 11 13 15 17 19
QueueFull():1
QueueEmpty():1
QueueLength():0
EnQueue(20): 0 (0 Failed, 1 Success) 複制
QueueFull():1
、
EnQueue(20): 0
可以看出順序隊列存在假溢出（實際可用空間并未占滿，卻不能進行入隊操作）
例如：
1️⃣：初始化空隊列，
q -> front = q -> rear = 0
2️⃣：入隊a1、a2、a3，
q -> front = 0, q -> rear = 3
3️⃣：出隊a1、a2，
q -> front = 2, q -> rear = 3
4️⃣：入隊a4、a5、a6，
q -> front = 2, q -> rear = 6
執行 4️⃣ 操作後隊列的"尾指針"已經超出對隊列的最大範圍了，之後無法再進行入隊操作，而隊列實際空間并未占滿，就造成了假溢出。
用 循環隊列 就可以解決假溢出情況。
源代碼
源代碼已上傳到 GitHub Data-Structure-of-C，歡迎大家下載下傳 C語言實作資料結構