??本篇介紹有關佇列的知識，佇列也是一種特殊的線性表，只允許在表的表的一端進行插入，而在表的另一端進行洗掉，插入元素稱為入隊或進隊；洗掉元素稱為出隊或離隊，操作的特性是先進先出，
??佇列的常見操作和堆疊類似，有初始化佇列，佇列判空，入隊，出隊，讀隊頭元素，下面介紹佇列的順序存盤和鏈式存盤，
一：佇列的順序存盤
1.普通的順序存盤佇列
??實質是分配一塊連續的存盤單元存放佇列中的元素，并附設兩個指標，一個隊頭指標front指向隊頭元素，一個隊尾指標rear指向隊尾元素的下一個位置，也有其他的定義，操作是不同的，
??順序佇列描述為：
#define MaxSize 20 //定義佇列中元素的最大個數
typedef struct{
ElemType data[MaxSize]; //存放佇列元素
int front,rear; //隊頭指標和隊尾指標
}SqQueue;
??初始狀態(隊空)： Q.front == Q.rear == 0，
??進隊操作：隊不滿時，先先送值到隊尾元素，隊尾指標再加一，
??出隊操作：隊不空時，先取隊頭元素值，再將隊頭指標加一，
??但是這種簡單的佇列會出現假溢位的現象，是因為隊滿時Q.front仍然等于Q.rear，如何進行改進呢，可以用一種叫做回圈佇列的存盤結構，
2.回圈佇列
??就使用一種環狀結構存盤佇列，當隊首指標Q.front在隊滿的位置MaxSize-1時，再前進一個位置就自動回到0，這時候可以用取余操作%來實作，
??初始時：Q.front==Q.rear=0，
??隊首指標加一：Q.front=(Q.front+1)%MaxSize，
??隊尾指標加一：Q.rear=(Q.rear+1)%MaxSize，
??佇列長度：(Q.rear+MaxSize-Q.front)%MaxSize，
??出隊入隊時，指標都按順時針的方向進1，
??為了區別當Q.rear == Q.front時，是隊滿還是隊空，可以有三種處理方式，
??(1)犧牲一個存盤單元區分隊慷訓是隊滿，即入隊的時候少用一個佇列單元，則有
??隊空：Q.front == Q.rear
??隊滿：(Q.rear+1)%MaxSize == Q.front
??佇列中元素個數：(Q.rear+MaxSize-Q.front)%MaxSize
??(2)用一個計數器計算元素個數
??(3)用一個tag資料成員區分隊慷訓是隊滿,tag為0時隊空，tag為1時隊滿，
??操作如下：
??初始化：
void InitQueue(SqQueue &Q){
Q.rear = Q.front = 0; //初始化隊首，隊尾指標
}
??判隊空：
bool isEmpty(SqQueue Q){
if(Q.rear == Q.front) return true; //隊空條件
else return false;
}
??入隊：
bool EnQueue(SqQueue &Q,ElemType x){
if((Q.rear+1)%MaxSize == Q.front) return false; //隊滿則報錯
Q.data[Q.rear] = x;
Q.rear = (Q.rear+1)%MaxSize;
return true;
}
??出隊：
bool DeQueue(SqQueue &Q,ElemType &x){
if(Q.rear == Q.front) return false; //隊空則報錯
x = data[Q.front];
Q.front = (Q.front+1)%MaxSize;
return true;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/39761.html
標籤：其他