隊列

隊列是一種特殊的線性表，特殊之處在於它只允許在表的前端（front）進行刪除操作，而在表的後端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。

隊列的數據元素又稱為隊列元素。在隊列中插入一個隊列元素稱為入隊，從隊列中刪除一個隊列元素稱為出隊。因為隊列只允許在一端插入，在另一端刪除，所以只有最早進入隊列的元素才能最先從隊列中刪除，故隊列又稱為先進先出（FIFO—first in first out）線性表。 ^[1] 

建立順序隊列結構必須為其靜態分配或動態申請一片連續的存儲空間，並設置兩個指針進行管理。一個是隊頭指針front，它指向隊頭元素；另一個是隊尾指針rear，它指向下一個入隊元素的存儲位置，如圖所示

每次在隊尾插入一個元素時，rear增1； ^[4]  每次在隊頭刪除一個元素時，front增1。隨着插入和刪除操作的進行，隊列元素的個數不斷變化，隊列所佔的存儲空間也在為隊列結構所分配的連續空間中移動。當front=rear時，隊列中沒有任何元素，稱為空隊列。當rear增加到指向分配的連續空間之外時，隊列無法再插入新元素，但這時往往還有大量可用空間未被佔用，這些空間是已經出隊的隊列元素曾經佔用過得存儲單元。

順序隊列中的溢出現象：

（1） "下溢"現象：當隊列為空時，做出隊運算產生的溢出現象。“下溢”是正常現象，常用作程序控制轉移的條件。

（2）"真上溢"現象：當隊列滿時，做進棧運算產生空間溢出的現象。“真上溢”是一種出錯狀態，應設法避免。

（3）"假上溢"現象：由於入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠無法重新利用。當隊列中實際的元素個數遠遠小於向量空間的規模時，也可能由於尾指針已超越向量空間的上界而不能做入隊操作。該現象稱為"假上溢"現象。

在實際使用隊列時，為了使隊列空間能重複使用，往往對隊列的使用方法稍加改進：無論插入或刪除，一旦rear指針增1或front指針增1 時超出了所分配的隊列空間，就讓它指向這片連續空間的起始位置。自己真從MaxSize-1增1變到0，可用取餘運算rear%MaxSize和front%MaxSize來實現。這實際上是把隊列空間想象成一個環形空間，環形空間中的存儲單元循環使用，用這種方法管理的隊列也就稱為循環隊列。除了一些簡單應用之外，真正實用的隊列是循環隊列。 ^[2] 

在循環隊列中，當隊列為空時，有front=rear，而當所有隊列空間全佔滿時，也有front=rear。為了區別這兩種情況，規定循環隊列最多隻能有MaxSize-1個隊列元素，當循環隊列中只剩下一個空存儲單元時，隊列就已經滿了。因此，隊列判空的條件時front=rear，而隊列判滿的條件時front=（rear+1）%MaxSize。隊空和隊滿的情況如圖：

隊列可以用數組Q[1…m]來存儲，數組的上界m即是隊列所容許的最大容量。在隊列的運算中需設兩個指針：head，隊頭指針，指向實際隊頭元素；tail，隊尾指針，指向實際隊尾元素的下一個位置。一般情況下，兩個指針的初值設為0，這時隊列為空，沒有元素。數組定義Q[1…10]。Q(i) i=3,4,5,6,7,8。頭指針head=2，尾指針tail=8。隊列中擁有的元素個數為:L=tail-head。現要讓排頭的元素出隊，則需將頭指針加1。即head=head+1這時頭指針向上移動一個位置，指向Q(3)，表示Q(3)已出隊。如果想讓一個新元素入隊，則需尾指針向上移動一個位置。即tail=tail+1這時Q(9)入隊。當隊尾已經處理在最上面時，即tail=10，如果還要執行入隊操作，則要發生"上溢"，但實際上隊列中還有三個空位置，所以這種溢出稱為"假溢出"。

克服假溢出的方法有兩種。一種是將隊列中的所有元素均向低地址區移動，顯然這種方法是很浪費時間的；另一種方法是將數組存儲區看成是一個首尾相接的環形區域。當存放到n地址後，下一個地址就"翻轉"為1。在結構上採用這種技巧來存儲的隊列稱為循環隊列。

隊列和棧一樣只允許在斷點處插入和刪除元素。

循環隊的入隊算法如下：

1、tail=tail+1；

2、若tail=n+1，則tail=1；

3、若head=tail，即尾指針與頭指針重合了，表示元素已裝滿隊列，則作上溢出錯處理；

4、否則，Q(tail)=X，結束（X為新入出元素）。

隊列和棧一樣，有着非常廣泛的應用。

注意：（1）有時候隊列中還會設置表頭結點，就是在隊頭的前面還有一個結點，這個結點的數據域為空，但是指針域指向隊頭元素。

（2）另外，上面的計算還可以利用下面給出的公式cq.rear=(cq.front+1)/max;

當有表頭結點時，公式變為cq.rear=(cq.front+1)/（max+1）。

在隊列的形成過程中，可以利用線性鏈表的原理，來生成一個隊列。

基於鏈表的隊列，要動態創建和刪除節點，效率較低，但是可以動態增長。

隊列採用的FIFO(first in first out)，新元素（等待進入隊列的元素）總是被插入到鏈表的尾部，而讀取的時候總是從鏈表的頭部開始讀取。每次讀取一個元素，釋放一個元素。所謂的動態創建，動態釋放。因而也不存在溢出等問題。由於鏈表由結構體間接而成，遍歷也方便。

（1）初始化隊列：Init_Queue(q) ，初始條件：隊q 不存在。操作結果：構造了一個空隊；

（2）入隊操作： In_Queue(q,x),初始條件： 隊q 存在。操作結果： 對已存在的隊列q，插入一個元素x 到隊尾，隊發生變化；

（3）出隊操作： Out_Queue(q,x)，初始條件: 隊q 存在且非空，操作結果： 刪除隊首元素，並返回其值，隊發生變化；

（4）讀隊頭元素：Front_Queue(q,x)，初始條件: 隊q 存在且非空，操作結果： 讀隊頭元素，並返回其值，隊不變；

（5）判隊空操作：Empty_Queue(q)，初始條件： 隊q 存在，操作結果： 若q 為空隊則返回為1，否則返回為0。 ^[3] 

在STL中，對隊列的使用很是較完美

下面給出循環隊列的運算算法:

(1)將循環隊列置為空

//將隊列初始化

SeQueue::SeQueue()

{ front=0;

rear=0;

cout<<"init!"<<endl;

}

(2)判斷循環隊列是否為空

int SeQueue::Empty()

{ if(rear==front) return(1);

else return(0);

}

(3)在循環隊列中插入新的元素x

void SeQueue::AddQ(ElemType x)

{ if((rear+1) % MAXSIZE==front) cout<<" QUEUE IS FULL! "<<endl;

else{ rear=(rear+1) % MAXSIZE;

elem[rear]=x;

cout<<" OK!";

}

}

(4)刪除隊列中隊首元素

ElemType SeQueue::DelQ()

{ if(front==rear)

{ cout<<" QUEUE IS EMPTY! "<<endl; return -1;}

else{ front=(front+1) % MAXSIZE;

return(elem[front]);

}

}

(5)取隊列中的隊首元素

ElemType SeQueue::Front()

{ ElemType x;

if(front== rear)

cout<<"QUEUE IS EMPTY "<<endl;

else x= elem[(front+1)%MAXSIZE];

return (x);

}