隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。
簡介
隊列的數據元素又稱為隊列元素。在隊列中插入一個隊列元素稱為入隊，從隊列中刪除一個隊列元素稱為出隊。因為隊列只允許在一段插入，在另一端刪除，所以只有最早進入隊列的元素才能最先從隊列中刪除，故隊列又稱為先進先出（FIFO—first?in?first?out）線性表。
順序隊列
建立順序隊列結構必須為其靜態分配或動態申請一片連續的存儲空間，并設置兩個指針進行管理。一個是隊頭指針front，它指向隊頭元素；另一個是隊尾指針rear，它指向下一個入隊元素的存儲位置，如圖所示
每次在隊尾插入一個元素是，rear增1；每次隊頭刪除一個元素時，front增1。隨著插入和刪除操作的進行，隊列元素的個數不斷變化，隊列所占的存儲空間也在為隊列結構所分配的連續空間中國移動通信集團。當front=rear時，隊列中沒有任何元素，稱為空隊列。當rear增加到指向分配的連續空間之外時，隊列無法再插入新元素，但這時往往還有大量可用空間未被占用，這些空間是已經出隊的隊列元素曾經占用過得存儲單元。
順序隊列中的溢出現象：
（1）"下溢"現象：當隊列為空時，做出隊運算產生的溢出現象。“下溢”是正?，F象，常用作程序控制轉移的條件。
（2）"真上溢"現象：當隊列滿時，做進棧運算產生空間溢出的現象?！罢嫔弦纭笔且环N出錯狀態，應設法避免。
（3）"假上溢"現象：由于入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠無法重新利用。當隊列中實際的元素個數遠遠小于向量空間的規模時，也可能由于尾指針已超越向量空間的上界而不能做入隊操作。該現象稱為"假上溢"現象。
循環隊列
在實際使用隊列時，為了使隊列空間能重復使用，往往對隊列的使用方法稍加改進：無論插入或刪除，一旦rear指針增1或front指針增1時超出了所分配的隊列空間，就讓它指向這片連續空間的起始位置。自己真從Max開本1增1變到0，可用取余運算rear%MaxSize和front%MaxSize來實現。這實際上是把隊列空間想象成一個環形空間，環形空間中的存儲單元循環使用，用這種方法管理的隊列也就稱為循環隊列。除了一些簡單應用之外，真正實用的隊列時循環隊列。
在循環隊列中，當隊列為空時，有front=rear，而當所有隊列空間全占滿時，也有front=rear。為了區別這兩種情況，規定循環隊列最多只能有Max開本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，尾指針符尾=8。隊列中擁有的元素個數為:L=tail-head?，F要讓排頭的元素出隊，則需將頭指針加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=符尾，即尾指針與頭指針重合了，表示元素已裝滿隊列，則作上溢出錯處理；
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。
在STL中，對隊列的使用很是較完美
下面給出循環隊列的運算算法:
(1)將循環隊列置為空
//將隊列初始化
SeQueue::SeQueue()
{?front=0;
rear=0;
cout<<"init!"< } (2)判斷循環隊列是否為空 int?SeQueue::Empty() else?return(0); } (3)在循環隊列中插入新的元素x void?SeQueue::AddQ(ElemType?x) {?if((rear+1)?%?MAXSIZE==front)?cout<<"?QUEUE?IS?FULL!?"< else{?rear=(rear+1)?%?MAXSIZE; elem[rear]=x; cout<<"?OK!"; } } (4)刪除隊列中隊首元素 ElemType?SeQueue::DelQ() {?if(front==rear) {?cout<<"?QUEUE?IS?EMPTY!?"< else{?front=(front+1)?%?MAXSIZE; } } (5)取隊列中的隊首元素 ElemType?SeQueue::Front() {?ElemType?x; if(front==?rear) cout<<"QUEUE?IS?EMPTY?"< else?x=?elem[(front+1)%MAXSIZE]; return?(x); } 參考資料 > 電腦知識與技術-2005年15期-知網空間.-.2021-11-01