1. 佇列定義：
- 一種可以實作 “先進先出” 的存盤結構（類似于排隊）
- 只允許在一端插入元素，在另一端洗掉元素，不可以混在一起
2. 佇列分類：
- 鏈式佇列：由鏈表實作的佇列，本質是鏈表
- 靜態佇列：由陣列實作的佇列，本質是陣列
3. 回圈佇列講解
- 靜態佇列為什么必須時回圈佇列：靜態佇列必須是回圈佇列，這是由陣列的特性決定的，佇列只允許尾部添加元素頭部洗掉元素，如果用陣列實作，添加元素時元素向后排列，洗掉元素時前面的位置就會空出來，時間長了之后會造成大量的空間浪費，所以要使用回圈佇列，以防止空間浪費
非回圈佇列，會浪費很多空間
回圈佇列，不會浪費空間 - 回圈佇列需要幾個引數來確定：兩個，即佇列頭、尾（實質上就是陣列的兩個下標）
- 回圈佇列各個引數的含義：
- 回圈佇列需要兩個引數來確定，且這兩個引數在不同的情況下由不同的含義
- 佇列初始化時：front和rear值都為零
- 佇列非空時：front代表佇列第一個元素，rear代表佇列的最后一個有效元素的下一個元素
- 佇列空時：front和rear相等單不一定為零
- 回圈佇列入隊偽演算法講解：將值存入下標為rear的位置后,rear = (rear+1) %陣列長度，而不是 rear+1
- 回圈佇列出隊偽演算法講解：front = (front + 1) % 陣列長度，與入隊相同
- 如何判斷回圈佇列是否為空：若 rear == front 則佇列為空
- 如何判斷回圈佇列是否為滿：若 （rear + 1）% 陣列長度 == front 則佇列已滿（因為 rear 指示的是佇列最后一個有效元素的下一個元素，所以這樣判斷佇列已滿會浪費一個陣列位置，但是這已經比非回圈佇列省了很多空間了，如果要不浪費哪一個元素就需要多加一個引數，這樣就會麻煩很多，沒有必要）
4. 回圈佇列實作及細節
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct Queue{
int *pBase; //指向陣列的指標
int front; //佇列頭，數值尾佇列第一個有效元素的下標
int rear; //佇列尾，數值尾佇列最后一個有效元素的下一個元素的下標
}QUEUE,*PQUEUE;
PQUEUE InitQueue(void);
/**操作結果：構造一個空佇列Q */
void DestoryQueue(PQUEUE pQ);
/**初始條件：佇列已經存在
* 操作結果：佇列被銷毀
*/
void ClearQueue(PQUEUE pQ);
/**初始條件：佇列已經存在
* 操作結果：將佇列清空
*/
bool QueueEmpty(PQUEUE pQ);
/**初始條件：佇列已經存在
* 操作結果：若佇列為空，回傳TURE，否則回傳FALSE
*/
bool QueueFull(PQUEUE pQ);
/**初始條件：佇列已存在
* 操作結果：若佇列已滿，回傳TURE，否則回傳FALSE
*/
int QueueHead(PQUEUE pQ,int val);
/**初始條件：佇列存在且非空
* 操作結果：回傳佇列頭元素
*/
bool EnQueue(PQUEUE pQ,int val);
/**初始條件：佇列已存在
* 操作結果：在隊尾插入元素
*/
bool DeQueue(PQUEUE pQ,int *pVal);
/**初始條件：佇列存在且非空
* 操作結果：洗掉隊頭元素，并回傳其值
*/
void QueueTraverse(PQUEUE pQ);
/**初始條件：佇列存在且非空
* 操作結果：輸出佇列元素
*/
int N; //N 用于在各個函式之間傳遞佇列的實際長度
int main()
{
int t;
printf("請輸入佇列長度："); //這里用 N + 1 是因為輸入的佇列長度是實際元素的個數，因為回圈佇列會浪費一個元素，所以令佇列的實際長度為 N + 1 方便使用
scanf("%d",&t);
N=t+1;
PQUEUE pQ=InitQueue();
int i,n;
for(i=0;i<N-1;i++){ //用戶輸入的佇列長度為 N - 1
scanf("%d",&n);
EnQueue(pQ,n);
}
QueueTraverse(pQ);
int val;
DeQueue(pQ,&val);
QueueTraverse(pQ);
printf("出隊元素為：%d",val);
}
PQUEUE InitQueue(void) //構造一個空佇列
{
PQUEUE pQ=(PQUEUE)malloc(sizeof(QUEUE)); //這里必須用 malloc 函式，否則生成的就是一個區域變數，在這里錯了好幾次，應當注意！！
pQ->pBase=(int *)malloc(sizeof(int)*N);
pQ->rear=0; //因為這是一個空佇列，其中沒有任何有效元素，所以 rear 和 front 的值都為零
pQ->front=0;
return pQ;
}
void DestoryQueue(PQUEUE pQ) //銷毀佇列
{
free(pQ);
}
void ClearQueue(PQUEUE pQ) //清空佇列
{
pQ->front=pQ->rear; //清空佇列時并不需要將佇列里所有元素都重置為零，只需要令 front 與 rear 的值相同即可，以后入隊時輸入的值就會把原來的值覆寫
}
bool QueueEmpty(PQUEUE pQ) //判斷佇列是否為空
{
if(pQ->front==pQ->rear){
return true;
}else{
return false;
}
}
bool QueueFull(PQUEUE pQ) //判斷佇列是否已滿
{
int m,n;
m=pQ->rear;
n=pQ->front;
if((m+1)%N==(n)) {
return true;
}else{
return false;
}
}
int QueueHead(PQUEUE pQ,int val) //回傳佇列頭元素
{
val=pQ->pBase[pQ->front];
return val;
}
bool EnQueue(PQUEUE pQ,int val) //在隊尾插入元素
{
if(QueueFull(pQ)){
return false;
}else{
pQ->pBase[pQ->rear]=val;
pQ->rear=(pQ->rear+1)%N;
return true;
}
}
bool DeQueue(PQUEUE pQ,int *pVal) //洗掉隊頭元素并回傳其值
{
if(QueueEmpty(pQ)){
return false;
} else{
*pVal=pQ->pBase[pQ->front]; //這里因為需要函式型別為 bool ，所以無法正常回傳 int 型別的值，所以用指標直接修改 val 的值即可
pQ->front=(pQ->front+1)%N;
return true;
}
}
void QueueTraverse(PQUEUE pQ) //遍歷輸出佇列元素
{
int i=pQ->front;
while(i!=pQ->rear){
printf("%d ",pQ->pBase[i]);
i=(i+1)%N;
}
printf("\n");
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/17885.html
標籤：其他