1.4　棧和隊列

考點1　棧及其基本運算

（1）棧的定義

棧是限定在一端進行插入與刪除的線性表。

（2）棧的特點：

①允許插入和刪除的一端稱為棧頂，不允許插入與刪除的一端稱為棧底。棧頂元素總是最后被插入的元素，也是最先被刪除的元素；棧底元素總是最先被插入也是最后被刪除的。

②棧遵循“先進后出”或“后進先出”的原則，具有記憶功能。

③通常用指針top來指示棧頂位置，用指針bottom指向棧底，棧頂指針top動態反映了棧中元素的變化情況。

（3）棧的順序存儲及其運算

在棧的順序存儲空間S（1：m）中，top＝0表示棧空；top＝m表示棧滿。

棧的三種運算：

①入棧運算

入棧運算是指在棧頂位置插入一個新元素。操作過程如下：

a．首先判斷棧頂指針是否已經指向存儲空間的最后一個位置。如果是，則說明棧空間已滿，不可能再進行入棧操作（這種情況稱為棧“上溢”錯誤），算法結束。

b．然后將棧頂指針進一（即top加1）。

c．最后將新元素x插入棧頂指針指向的位置。

②退棧運算

退棧運算是指取出棧頂元素并賦給一個指定的變量。操作過程如下：

a．首先判斷棧頂指針是否為0。如果是，則說明棧空，不可能進行退棧操作（這種情況稱為棧“下溢”錯誤），算法結束。

b．然后將棧頂元素（棧頂指針指向的元素）賦給一個指定的變量。

c．最后將棧頂指針退一（即top減1）。

③讀棧頂元素

讀棧頂元素是指將棧頂元素賦給一個指定的變量。操作過程如下：

a．首先判斷棧頂指針是否為0。如果是，則說明棧空，讀不到棧頂元素，算法結束。

b．然后將棧頂元素賦給指定的變量y。

這個運算不刪除棧頂元素，只是將它的值賦給一個變量，棧頂指針不會變。

【真題演練】

1支持子程序調用的數據結構是（　　）。[2013年9月真題]

A．棧

B．樹

C．隊列

D．二叉樹

【答案】A

【解析】在高級語言中，函數的調用是通過棧來實現的。在進行函數調用時，系統將所需的信息壓入棧中，如函數的局部變量、返回值等。每個函數的狀態是由函數中的局部變量、函數參數值、函數的返回值地址決定的，存儲這些信息的數據區域稱為活動記錄，或叫做棧幀，它是運行時系統棧上分配的空間。答案選擇A選項。

2下列與棧結構有關聯的是（　　）。[2013年3月真題]

A．數組的定義域使用

B．操作系統的進程調度

C．函數的遞歸調用

D．選擇結構的執行

【答案】C

【解析】函數的遞歸調用是指函數調用函數本身，直到滿足特定條件時終止，然后從最后被遞歸調用處返回。遞歸函數是通過棧來實現的，所以調用原則和棧的實現相一致。所以遞歸函數是通過棧來實現的。答案選擇C選項。

3設棧的順序存儲空間為S（1：50），初始狀態為top=0。現經過一系列入棧與退棧運算后，top=20，則當前棧中的元素個數為（　　）。[2014年3月真題]

A．30

B．29

C．20

D．19

【答案】C

【解析】棧按照“先進后出”的原則組織數據，插入與刪除操作被限制在棧頂一端進行，入棧使棧頂位置進1，退棧使棧頂退1。top=0表示棧為空，在運算過程中，指針始終指向棧頂元素。top=20，說明當前棧中有20個元素。答案選擇C選項。

4一個棧的初始狀態為空。現將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是（　　）。[2013年9月真題]

A．12345ABCDE

B．EDCBA54321

C．ABCDE12345

D．54321FDCBA

【答案】B

【解析】棧是按照“先進后出”的原則組織數據的，入棧的順序為12345ABCDE，則依次出棧的順序應為其逆序，即EDCBA54321。答案選擇B選項。

考點2　隊列及其基本運算

（1）什么是隊列

隊列（Queue）是指允許在一端進行插入、而在另一端進行刪除的線性表。

（2）隊列的特點

①允許插入的一端稱為隊尾，用隊尾指針指向隊尾元素；允許刪除的一端稱為隊頭，用排頭指針指向排頭元素的前一個位置。

②最先插入的元素最先被刪除，最后插入的元素最后被刪除，遵循“先進先出”或“后進后出”原則。

③隊尾指針rear和排頭指針front共同反映隊列中元素變動情況。

④入隊運算指只涉及隊尾指針rear變化，退隊運算只涉及排頭指針front變化。

（3）循環隊列及其運算

循環隊列是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。在循環隊列中，用隊尾指針rear指向隊尾元素，用排頭指針front指向排頭元素的前一個位置，從排頭指針front指向的后一個位置到隊尾指針rear指向的位置均是隊列中元素。隊列空的條件是s＝0；隊列滿的條件是s＝1且front＝rear。

隊列的兩種運算

假設循環隊列的初始狀態為空，即：s＝0，且front＝rear＝m。

①入隊運算

入隊運算是指在循環隊列的隊尾加入一個新元素。操作過程如下：

a．首先判斷循環隊列是否滿。當循環隊列非空（S＝1）且隊尾指針等于排頭指針時，說明循環隊列已滿，不能進行入隊運算。這種情況稱為“上溢”。此時算法結束。

b．然后將隊尾指針進一（即rear＝rear＋1），并當rear＝m＋1時置rear＝1。

c．最后將新元素x插入隊尾指針指向的位置，并且置循環隊列非空標志。

②退隊運算

退隊運算是指在循環隊列的排頭位置退出一個元素并賦給指定的變量。操作過程如下：

a．首先判斷循環隊列是否為空。當循環隊列為空（s＝0）時，不能進行退隊運算。這種情況稱為“下溢”。此時算法結束。

b．然后將排頭指針進一（即front＝front＋1），并當front＝m＋1時置front＝1。

c．再將排頭指針指向的元素賦給指定的變量。

d．最后判斷退隊后循環隊列是否為空。當front＝rear時置循環隊列空標志（即s＝0）。

【真題演練】

1下列敘述中正確的是（　　）。[2013年9月真題]

A．棧是“先進先出”的線性表

B．隊列是“先進后出”的線性表

C．循環隊列是非線性結構

D．有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構

【答案】D

【解析】有序的線性表既可采用順序存儲結構，也可以采用鏈式存儲結構。A項錯誤，棧是“先進后出”的線性表；B項錯誤，隊列是“先進先出”的線性表；C項錯誤，循環隊列是線性結構的，有序的線性表既可采用順序存儲結構，也可采用鏈式存儲結構。答案選擇D選項。

2下列敘述中正確的是（　　）。[2014年3月真題]

A．循環隊列是順序存儲結構

B．循環隊列是鏈式存儲結構

C．循環隊列是非線性結構

D．循環隊列的插入運算不會發生溢出現象

【答案】A

【解析】A項正確，B項錯誤，循環隊列是一種順序存儲結構的隊列；C項錯誤，線性結構是一個非空序列：除第一個元素外，每個元素，有且只有一個前件；除最后一個元素外，每個元素有且只有一個后件，所以循環隊列是線性結構；D項錯誤，當循環隊列的元素個數等于存儲長度后，入隊會發生溢出現象，覆蓋前面的數據。答案選擇A選項。

3對于循環隊列，下列敘述中正確的是（　　）。[2013年9月真題]

A．隊頭指針是固定不變的

B．隊頭指針一定大于隊尾指針

C．隊頭指針一定小于隊尾指針

D．隊頭指針可以大于隊尾指針，也可以小于隊尾指針

【答案】D

【解析】在循環隊列中，用隊尾指針（rear）指向隊列中的隊尾元素，用隊頭指針（front）指向隊頭元素的前一個位置。在循環隊列中，一般情況下rear>front，當存儲空間的最后一個位置被使用，而新元素要入隊時，如果存儲空間的第一個位置空閑，便可將元素插入到第一個位置，此時存儲空間的第一個位置作為隊尾，便有front>rear。所以答案選擇D選項。

4下列敘述中正確的是（　　）。[2013年9月真題]

A．循環隊列有隊頭和隊尾兩個指針，因此，循環隊列是非線性結構

B．在循環隊列中，只需要隊頭指針就能反映隊列中元索的動態變化情況

C．在循環隊列中，只需要隊尾指針就能反映隊列中元素的動態變化情況

D．循環隊列中元素的個數是由隊頭指針和隊尾指針共同決定

【答案】D

【解析】循環隊列是順序存儲的線性結構，是隊列常采用的形式，故A項錯誤。循環隊列中的元素是動態變化的：每一次入隊，隊尾指針就進一；每一次出隊，隊頭指針就進一，所以隊頭指針和隊尾指針一起反映了隊列中元素的動態變化情況，BC兩項錯誤。從隊頭指針指向的后一個位置與隊尾指針指向的位置之間的元素即為隊列中所有的元素，答案選擇D選項。