3.2 隊列

3.2.1 隊列的基本概念

隊列（簡稱隊）也是一種運算受限的線性表，在這種特殊的線性表上，插入限定在表的某一端進行，刪除限定在表的另一端進行。隊列的插入操作稱為進隊，刪除操作稱為出隊。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。新插入的元素只能添加到隊尾，被刪除的只能是排在隊頭的元素。

正是這種受限的元素插入和刪除運算，使得隊列表現出先進先出或者后進后出的特點。舉一個例子進行說明，如圖3.13所示是顧客①～⑤排隊買車票的情況，排隊圍欄里能容納若干人，但每次只能容許一個人進出，進入排隊隊列只能從進口進，某顧客買完車票后只能從出口出。從中看到，顧客進入排隊隊列的順序是①～⑤，那么買票并離開隊列的順序也只能是①～⑤。也就是說，顧客進出排隊隊列的原則是先進去的先出來。

歸納起來，一個隊列的示意圖如圖3.14所示。

隊列的基本運算如下。

（1）初始化隊列InitQueue（qu）：建立一個空隊qu。

（2）銷毀隊DestroyQueue（qu）：釋放隊列qu占用的內存空間。

（3）進隊EnQueue（qu，x）：將x插入到隊列qu的隊尾。

（4）出隊DeQueue（qu，x）：將隊列qu的隊頭元素出隊并賦給x。

（5）取隊頭元素GetHead（qu，x）：取出隊列qu的隊頭元素并賦給x，但該元素不出隊。

（6）判斷隊空QueueEmpty（qu）：判斷隊列qu是否為空。

包含基本運算的隊列如圖3.15所示，其中，op1～op6表示上述6個基本運算。

【例3.10】以下屬于隊列的基本運算的是________。

A．對隊列中的元素排序

B．取出最近進隊的元素

C．在隊列中某元素之前插入元素

D．刪除隊頭元素

解：刪除隊頭元素即出隊，屬隊列的一種基本運算，其他均不是隊列的基本運算。本題答案為D。

【例3.11】設棧S和隊列Q的初始狀態均為空，元素a、b、c、d、e、f、g依次進入棧S。若每個元素出棧后立即進入隊列Q，且7個元素出列的順序是b、d、c、f、e、a、g，則棧S的容量至少是________。

A．1

B．2

C．3

D．4

解：由于隊列不改變進、出隊元素的次序，即a1、a2、…、an依次進入一個隊列，出隊序列只有a1、a2、…、an一種，所以本題變為通過一個棧將a、b、c、d、e、f、g序列變為b、d、c、f、e、a、g序列時?？臻g至少多大。其過程如表3.1所示，從中可以看到，棧中最多有三個元素，即棧大小至少為3。本題答案為C。

3.2.2 隊列的順序存儲結構

與棧類似，隊列通常有兩種存儲結構，即順序存儲結構和鏈式存儲結構。隊列的順序存儲結構簡稱為順序隊，它由一個一維數組（用于存儲隊列中元素）及兩個分別指示隊頭和隊尾的變量組成（因為隊列不同于棧，棧只要一端發生改變，而隊列的兩端都可能發生改變），這兩個變量分別稱為“隊頭指針”和“隊尾指針”。通常約定隊尾指針指示隊尾元素的當前位置，隊頭指針指示隊頭元素的前一個位置。

順序隊的類型聲明如下。

順序隊的定義為一個結構類型，該類型變量有三個域：data、front、rear。其中，data為存儲隊列中元素的一維數組。隊頭指針front和隊尾指針rear定義為整型變量，實際取值范圍是0～MaxSize—1。

圖3.16表示了順序隊列sq（假設MaxSize=5）的幾種狀態。

圖3.16（a）表示隊列的初始狀態，sq.rear=sq.front=—1。

圖3.16（b）表示元素a進隊后，sq.rear=0，sq.front=—1。

圖3.16（c）表示元素b、c、d、e依次進隊后，sq.rear=4，sq.front=—1。

圖3.16（d）表示元素a、b出隊后，sq.rear=4，sq.front=1。

圖3.16（e）表示元素c、d、e出隊后，sq.rear=sq.front=4。

從圖3.16中可以看到，在隊列剛建立時，先對它進行初始化，令front=rear=—1。每當進隊一個元素時，讓隊尾指針rear增1，再將新元素放在rear所指位置，也就是說元素進隊只會引起rear的變化，而不會導致front的變化，而且rear指示剛進隊的元素（隊尾元素）位置。隊頭指針front則不同，每當出隊一個元素時，讓隊頭指針front增1，再把front所指位置上的元素取出，也就是說元素出隊只會引起front的變化，而不會導致rear的變化，而且front所指示的元素已出隊了，它實際指示的是當前隊列中隊頭元素的前一位置。

從圖3.16中可以看到，圖3.16（a）和圖3.16（e）都是隊空的情況，均滿足front==rear的條件，所以可以將front==rear作為隊空的條件。那么隊滿的條件如何設置呢？受順序棧的啟發，似乎很容易得到隊滿的條件為rear==MaxSize—1。顯然這里有問題，因為圖3.16（d）和圖3.16（e）都滿足這個“隊滿”的條件，而實際上隊列并沒有滿，這種因為隊滿條件設置不合理而導致的“溢出”稱為假溢出，也就是說這種“溢出”并不是真正的溢出，盡管隊滿條件成立了，但隊列中還有多個存放元素的空位置。

為了能夠充分地使用數組中的存儲空間，可以把數組的前端和后端連接起來，形成一個環形的表，即把存儲隊列元素的表從邏輯上看成一個環，這個環形的表叫作循環隊列或環形隊列。圖3.17表示了循環隊列sq的幾種狀態。

圖3.17（a）表示隊列的初始狀態，sq.rear=sq.front=0。

圖3.17（b）表示元素a進隊后，sq.rear=1，sq.front=0。

圖3.17（c）表示元素b、c、d、e依次進隊后，sq.rear=0，sq.front=0。

圖3.17（d）表示元素a、b出隊后，sq.rear=0，sq.front=2。

圖3.17（e）表示元素c、d，e出隊后，sq.rear=sq.front=0。

循環隊列首尾相連，當隊頭指針front==MaxSize—1后，再前進一個位置就自動到0，這可以利用除法取余的運算（MOD，C/C++語言中運算符為%）來實現。所以隊頭隊尾指針進1的操作如下。

隊頭指針進1：front=（front+1）MOD MaxSize

隊尾指針進1：rear=（rear+1）MOD MaxSize

循環隊列的隊頭指針和隊尾指針初始化時都置為0：front=rear=0。在隊尾插入新元素和刪除隊頭元素時，相關指針都循環進1。當它們進到MaxSize—1時，并不表示隊空間滿了，只要有需要，利用MOD運算可以前進到數組的0號位置。

如果循環隊列讀取元素的速度快于存入元素的速度，隊頭指針會很快追上隊尾指針，一旦到達front==rear時，則隊列變成空隊列。反之，如果隊列存入元素的速度快于讀取元素的速度，隊尾指針很快就會趕上隊頭指針，一旦隊列滿就不能再加入新元素了。

在循環隊列中仍不能區分隊空和隊滿，因為圖3.17（a）、圖3.17（c）和圖3.17（e）都滿足條件front==rear，而圖3.17（a）和圖3.17（e）為隊空，圖3.17（c）為隊滿。那么如何解決這一問題呢？仍設置隊空條件為front==rear，將隊滿條件設置為（rear+1）MOD MaxSize== front，也就是說，當rear指到front的前一位置時就認為隊列滿了，顯然在這樣設置的隊滿條件下，隊滿條件成立時隊中還有一個空閑單元，也就是說這樣的隊中最多只能進隊MaxSize—1個元素。

說明：上述設置循環隊列隊滿條件的方法不是最理想的，因為隊中最多只能放入MaxSize—1個元素，但它是一種最簡單的方法，后面例3.15就在這個基礎上進行了改進，讀者可以體會兩種方法的差異。

歸納起來，上述設置的循環隊列sq的4個要素如下。

（1）隊空條件：sq.front==sq.rear。

（2）隊滿條件：（sq.rear+1）%MaxSize==sq.front。

（3）進隊操作：sq.rear循環進1；元素進隊。

（4）出隊操作：sq.front循環進1；元素出隊。

循環隊列的基本運算算法如下。

1．初始化隊列運算算法

其主要操作是：設置sq.front=sq.rear=0。對應的算法如下。

2．銷毀隊列運算算法

這里順序隊的內存空間是由系統自動分配的，在不再需要時由系統自動釋放其空間。對應的算法如下。

      void DestroyQueue(SqQueue sq)
      {  }

3．進隊運算算法

其主要操作是：先判斷隊列是否已滿，若不滿，讓隊尾指針循環進1，在該位置存放x。對應的算法如下。

4．出隊運算算法

其主要操作是：先判斷隊列是否已空，若不空，讓隊頭指針循環進1，將該位置的元素值賦給x。對應的算法如下。

5．取隊頭元素運算算法

其主要操作是：先判斷隊列是否已空，若不空，將隊頭指針前一個位置的元素值賦給x。對應的算法如下。

6．判斷隊空運算算法

其主要操作是：若隊列為空，則返回1；否則返回0。對應的算法如下。

      int QueueEmpty(SqQueue sq)
      {   if(sq.rear==sq.front)return 1;
          else return 0;
      }

提示：將順序隊類型聲明及其基本運算函數存放在SqQueue.cpp文件中。

當順序隊的基本運算函數設計好后，給出以下程序調用這些基本運算函數，讀者可以對照程序執行結果進行分析，進一步體會順序隊的各種運算的實現過程。

上述程序的執行結果如圖3.18所示。

說明：順序隊有循環隊列和非循環隊列兩種，前者把存儲隊列元素的表從邏輯上看成一個環，從而新進隊的元素可以覆蓋已出隊元素的空間，提高存儲空間利用率。但有些情況下要利用所有進隊的元素求解時，只能采用非循環隊列。

【例3.12】若用一個大小為6的數組來實現循環隊列，隊頭指針front指向隊列中隊頭元素的前一個位置，隊尾指針rear指向隊尾元素的位置。若當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為________。

A．1和5

B．2和4

C．4和2

D．5和1

解：當前有rear=0，進隊兩個元素后，rear循環遞增2，rear=2；當前有front=3，出隊一個元素后，front循環遞增1，front=4。本題答案為B。

【例3.13】對于循環隊列，寫出求隊列中元素個數的公式，并編寫相應的算法。

解：循環隊列中隊頭、隊尾指針變化主要有如圖3.19所示的兩種情況，歸納起來，循環隊列元素個數的計算公式如下。

（rear—front+MaxSize）%MaxSize

對應的算法如下。

      int Count(SqQueue sq)
      {
           return(sq.rear—sq.front+MaxSize) % MaxSize;
      }

【例3.14】已知循環隊列存儲在一維數組A[0..n—1]中，且隊列非空時front和rear分別指向隊頭元素和隊尾元素。若初始時隊列空，且要求第一個進入隊列的元素存儲在A[0]處，則初始時front和rear的值分別是________。

A．0，0

B．0，n—1

C．n—1，0

D．n—1，n—1

解：在循環隊列中，進隊操作是隊尾指針rear循環加1，再在該處放置進隊的元素，本題要求第一個進入隊列的元素存儲在A[0]處，則rear應為n—1，因為這樣有（rear+1）%n=0。而隊頭指針front指向隊頭元素，此時隊頭位置為0，所以front的初值為0。本題答案為B。

提示：在一般的數據結構教科書中，循環隊列的隊頭指針front設計為指向隊列中隊頭元素的前一個位置，而隊尾指針rear指向隊尾元素的位置，本題的front和rear有所不同。

【例3.15】如果用一個大小為MaxSize的數組表示環形隊列，該隊列只有一個隊頭指針front，不設隊尾指針rear，而改置一個計數器count，用以記錄隊列中的元素個數。

（1）隊列中最多能容納多少個元素？

（2）設計實現隊列基本運算的算法。

解：依題意，設計隊列的類型如下。

（1）隊列中最多可容納MaxSize個元素，因為這里不需要空出一個位置以區分隊列空和隊列滿的情況。

（2）隊列sq為空的條件是：sq.count==0；隊列為滿的條件是：sq.count==MaxSize。在隊頭指針sq.front和隊中元素個數sq.count已知時，計算隊尾元素的位置的公式是：

隊尾元素位置=（sq.front+sq.count）%MaxSize

在這種隊列上實現隊列的基本運算算法如下。

3.2.3 隊列的鏈式存儲結構

隊列的鏈式存儲結構簡稱為鏈隊，它實際上是一個同時帶有隊頭指針front和隊尾指針rear的單鏈表。隊頭指針指向隊頭結點，隊尾指針指向隊尾結點即單鏈表的最后一個結點，并將隊頭和隊尾指針結合起來構成鏈隊結點，如圖3.20所示。

其中，鏈隊的數據結點類型聲明如下。

鏈隊結點的類型聲明如下。

在這樣的鏈隊中，隊空的條件是lq—>front==NULL或lq—>rear==NULL（這里采用lq—>front==NULL的隊空條件）。一般情況下，鏈隊是不會出現隊滿的情況的。歸納起來，鏈隊lq的4個要素如下。

（1）隊空條件：lq—>front==NULL。

（2）隊滿條件：不考慮（因為每個結點是動態分配的）。

（3）進隊操作：創建結點p，將其插入到隊尾，并由lq—>rear指向它。

（4）出隊操作：刪除隊頭結點。

在鏈隊上實現隊列基本運算算法如下。

1．初始化隊列運算算法

其主要操作是：創建鏈隊結點，并置該結點的rear和front均為NULL。對應的算法如下。

2．銷毀隊列運算算法

鏈隊的所有結點空間都是通過malloc函數分配的，在不再需要時需通過free函數釋放所有結點的空間。在銷毀隊列lq時，先像釋放單鏈表一樣釋放隊中所有數據結點，然后釋放鏈隊結點lq。對應的算法如下。

3．進隊運算算法

其主要操作是：創建一個新結點s，將其鏈接到鏈隊的末尾，并由rear指向它。對應的算法如下。

4．出隊運算算法

其主要操作是：將front指向結點的data域值賦給x，并刪除該結點。對應的算法如下。

5．取隊頭元素運算算法

其主要操作是：將front指向結點的data域值賦給x。對應的算法如下。

6．判斷隊空運算算法

其主要操作是：若鏈隊為空，則返回1；否則返回0。對應的算法如下。

提示：將鏈隊結點類型聲明及其基本運算函數存放在LinkQueue.cpp文件中。

當鏈隊的基本運算函數設計好后，給出以下程序調用這些基本運算函數，讀者可以對照程序執行結果進行分析，進一步體會鏈隊的各種運算的實現過程。

上述程序的執行結果如圖3.18所示。

【例3.16】若使用不帶頭結點的循環鏈表來表示隊列，lq是這樣的鏈表中尾結點指針，如圖3.21所示。試基于此結構給出隊列的相關運算算法。

解：這里使用的循環鏈表不帶頭結點，lq始終指向隊尾結點，lq—>next即為隊頭結點。當lq==NULL時隊列為空，lq—>next==lq表示隊列中只有一個結點。隊列的相關運算算法如下。

【例3.17】以下各種不帶頭結點的鏈表中最不適合用作鏈隊的是________。

A．只帶隊首指針的非循環雙鏈表

B．只帶隊首指針的循環雙鏈表

C．只帶隊尾指針的循環雙鏈表

D．只帶隊尾指針的循環單鏈表

解：隊列最基本的運算是進隊和出隊。鏈隊的隊頭和隊尾分別在鏈表的前、后端，即進隊在鏈尾進行，出隊在鏈首進行。

對于選項A的只帶隊首指針的非循環雙鏈表，在末尾插入一個結點（進隊）的時間復雜度為O（n），其他選項的鏈表完成同樣操作的時間復雜度均為O（1），所以相比較而言，選項A的存儲結構最不適合用作鏈隊。本題答案為A。

3.2.4 隊列的應用示例

在較復雜的數據處理過程中，通常需要保存多個臨時產生的數據，如果先產生的數據先進行處理，那么需要用隊列來保存這些數據。下面通過一個典型示例說明隊列的應用。

【例3.18】設計一個程序，反映病人到醫院看病、排隊看醫生的過程。

解：（1）設計存儲結構。

病人排隊看醫生采用先到先看的方式，所以要用到一個隊列。由于病人人數具有較大的不確定性，這里采用一個帶頭結點的單鏈表作為隊列的存儲結構。為了簡單，病人通過其姓名來唯一標識。例如，有Smith、John和Mary三個病人依次排隊的病人隊列如圖3.22所示。

病人鏈隊結點類型如下。

病人鏈隊中的結點類型如下。

（2）設計運算算法。

在病人隊列設計好后，設計相關的基本運算算法，如隊列初始化、進隊和出隊等，這些算法如下。

（3）設計主函數。

然后設計如下主函數通過簡單的提示性菜單方式來操作各個功能。

（4）執行結果。

本程序的一次執行結果如圖3.23所示。