1.4　棧和隊(duì)列

視頻二維碼（掃碼觀看）

一、棧及其基本運(yùn)算

1什么是棧

【定義】限定在一端進(jìn)行插入與刪除的線性表

【說(shuō)明】

①允許插入與刪除的一端稱為棧頂（指針top），而不允許插入與刪除的另一端稱為棧底（指針bottom）。

②棧是按照“先進(jìn)后出”（FILO）的原則組織數(shù)據(jù)。

③棧具有記憶作用。

④往棧中插入一個(gè)元素稱為入棧運(yùn)算，從棧中刪除一個(gè)元素（即刪除棧頂元素）稱為出棧運(yùn)算。

圖1-6　棧示意圖

2棧的順序存儲(chǔ)及其運(yùn)算

圖1-7（a）是容量為10的棧順序存儲(chǔ)空間，棧中已有6個(gè)元素；圖1-7（b）與圖1-7（c）分別為入棧與退棧后的狀態(tài)。

圖1-7　棧在順序存儲(chǔ)結(jié)構(gòu)下的運(yùn)算

（1）入棧運(yùn)算

入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素。操作過(guò)程如下：

①首先判斷棧頂指針是否已經(jīng)指向存儲(chǔ)空間的最后一個(gè)位置。如果是，則說(shuō)明棧空間已滿，不可能再進(jìn)行入棧操作（這種情況稱為?！吧弦纭卞e(cuò)誤），算法結(jié)束。

②然后將棧頂指針進(jìn)一（即top加1）。

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

（2）退棧運(yùn)算

退棧運(yùn)算是指取出棧頂元素并賦給一個(gè)指定的變量。操作過(guò)程如下：

①首先判斷棧頂指針是否為0。如果是，則說(shuō)明棧空，不可能進(jìn)行退棧操作（這種情況稱為?！跋乱纭卞e(cuò)誤），算法結(jié)束。

②然后將棧頂元素（棧頂指針指向的元素）賦給一個(gè)指定的變量。

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

（3）讀棧頂元素

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

①首先判斷棧頂指針是否為0。如果是，則說(shuō)明棧空，讀不到棧頂元素，算法結(jié)束。

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

【注意】這個(gè)運(yùn)算不刪除棧頂元素，只是將它的值賦給一個(gè)變量，因此，在這個(gè)運(yùn)算中棧頂指針不會(huì)改變。

【考題】下列關(guān)于棧的敘述中正確的是（　?。?。

A．在棧中只能插入數(shù)據(jù)

B．在棧中只能刪除數(shù)據(jù)

C．棧是先進(jìn)先出的線性表

D．棧是先進(jìn)后出的線性表

E．棧是一種非線性結(jié)構(gòu)

【答案】D

【解析】在棧中，只允許在棧頂一端進(jìn)行插入和刪除，所以A、B錯(cuò)誤；隊(duì)列是“先進(jìn)先出”的線性表，棧是“先進(jìn)后出”的線性表，所以C、E錯(cuò)誤，D正確。

二、隊(duì)列及其基本運(yùn)算

1什么是隊(duì)列

加入的元素總是插入到線性表的末尾，并且又總是從線性表的頭部取出（刪除）元素。這種線性表稱為隊(duì)列。

【說(shuō)明】

①允許插入的一端稱為隊(duì)尾（rear），允許刪除的一端稱為隊(duì)頭（front）。

②在隊(duì)列中按照“先進(jìn)先出”的原則進(jìn)行操作。

圖1-8　具有6個(gè)元素的隊(duì)列示意圖

圖1-9　隊(duì)列運(yùn)算示意圖

【考題】下列關(guān)于隊(duì)列的敘述中正確的是（　?。?/p>

A．在隊(duì)列中只能插入數(shù)據(jù)

B．在隊(duì)列中只能刪除數(shù)據(jù)

C．隊(duì)列是先進(jìn)先出的線性表

D．隊(duì)列是先進(jìn)后出的線性表

【答案】C

【解析】在隊(duì)列中，只允許在一端進(jìn)行插入，在另一端進(jìn)行刪除，所以A、B錯(cuò)誤；隊(duì)列是“先進(jìn)先出”的線性表，棧是“先進(jìn)后出”的線性表，所以D錯(cuò)誤，選擇C。

2循環(huán)隊(duì)列及其運(yùn)算

【定義】循環(huán)隊(duì)列是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。

圖1-10　循環(huán)隊(duì)列存儲(chǔ)空間示意圖

用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置。

在實(shí)際使用循環(huán)隊(duì)列時(shí)，為了能區(qū)分隊(duì)列滿還是隊(duì)列空，通常還需增加一個(gè)標(biāo)志s，s值的定義如下：

由此可以得出隊(duì)列空與隊(duì)列滿的條件如下：

隊(duì)列空的條件為s＝0；

隊(duì)列滿的條件為s＝1且front＝rear。

圖1-11　循環(huán)隊(duì)列運(yùn)算示意圖

（1）入隊(duì)運(yùn)算

入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素。操作過(guò)程如下：

①首先判斷循環(huán)隊(duì)列是否滿。當(dāng)循環(huán)隊(duì)列非空（S＝1）且隊(duì)尾指針等于排頭指針時(shí)，說(shuō)明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為“上溢”。此時(shí)算法結(jié)束。

②然后將隊(duì)尾指針進(jìn)一（即rear＝rear＋1），并當(dāng)rear＝m＋1時(shí)置rear＝1。

③最后將新元素x插入隊(duì)尾指針指向的位置，并且置循環(huán)隊(duì)列非空標(biāo)志。

（2）退隊(duì)運(yùn)算

退隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的排頭位置退出一個(gè)元素并賦給指定的變量。操作過(guò)程如下：

①首先判斷循環(huán)隊(duì)列是否為空。當(dāng)循環(huán)隊(duì)列為空（s＝0）時(shí)，不能進(jìn)行退隊(duì)運(yùn)算。這種情況稱為“下溢”。此時(shí)算法結(jié)束。

②然后將排頭指針進(jìn)一（即front＝front＋1），并當(dāng)front＝m＋1時(shí)置front＝1。

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

④最后判斷退隊(duì)后循環(huán)隊(duì)列是否為空。當(dāng)front＝rear時(shí)置循環(huán)隊(duì)列空標(biāo)志（即s＝0）。

【考題】設(shè)循環(huán)隊(duì)列為Q（1：m），其初始狀態(tài)為front＝rear＝m。經(jīng)過(guò)一系列入隊(duì)與退隊(duì)運(yùn)算后，front＝30，rear＝10?，F(xiàn)要在該循環(huán)隊(duì)列中作順序查找，最壞情況下需要比較的次數(shù)為（　?。?。

A．19

B．20

C．m－19

D．m－20

【答案】D

【解析】在該循環(huán)隊(duì)列中作順序查找，最壞情況下需要比較的次數(shù)，實(shí)際上就是求循環(huán)隊(duì)列中元素的個(gè)數(shù)。元素的個(gè)數(shù)＝（rear－front＋m）mod m＝（10－30＋m） mod m＝m－20，選項(xiàng)D正確。