（四）棧和隊(duì)列
1．棧及其基本運(yùn)算
1）棧
棧是一種特殊的線性表，它是限定在一端進(jìn)行插入和刪除的線性表。它的插入和刪除只能在表的一端進(jìn)行，而另一端是封閉的，不允許進(jìn)行插入和刪除操作。
在棧中，允許插入和刪除操作一端稱為棧頂，不允許插入和刪除操作的一端則稱為棧底。棧頂?shù)脑乜偸亲詈蟊徊迦氲脑?，也是最先被刪除的元素。它遵循的原則是：先進(jìn)后出或后進(jìn)先出。
堆棧指針總是指向棧頂元素的。
2）棧的順序存儲(chǔ)及其運(yùn)算
在棧的順序存儲(chǔ)空間S（1：m）中，S（bottom）通常為棧底元素，S（top）為棧頂元素。Top=0表示?？?；top=m表示棧滿。
1）入棧運(yùn)算
即在棧的頂部插入一個(gè)新元素。操作方式是：將棧頂指針加1，再將元素插入至指針?biāo)傅奈恢谩?BR> 2）退棧運(yùn)算
退棧運(yùn)算即將棧頂元素取出并賦給一個(gè)指定的變量。操作方式是：先將棧頂元素賦給指定的變量，再將棧頂指針減1。
3）讀棧頂元素
將棧頂元素賦給某一指定變量，但棧頂指針不變。
2．隊(duì)列及其基本運(yùn)算
1）隊(duì)列
隊(duì)列即是允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾，通常用一個(gè)尾指針指向隊(duì)尾；允許刪除的一端稱為隊(duì)首，通常用一個(gè)隊(duì)首指針指向排隊(duì)元素的前一個(gè)位置。
隊(duì)列遵循的規(guī)則是：先進(jìn)先出或后進(jìn)后出
2）循環(huán)隊(duì)列及其運(yùn)算
隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。
循環(huán)隊(duì)列，即是次隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用。
在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置，因此，從排頭指針front指向的后一個(gè)位置到隊(duì)尾指針rear指向的位置之間所有的元素均為隊(duì)列中的元素。
循環(huán)隊(duì)列的初始狀態(tài)為空，即rear=front=m。這里m即為隊(duì)列的存儲(chǔ)空間。
循環(huán)隊(duì)列的基本運(yùn)算：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算。
入隊(duì)運(yùn)算：每進(jìn)行一次入隊(duì)運(yùn)算，隊(duì)尾指針加1。當(dāng)隊(duì)尾指針rear=m+1時(shí)，即表示隊(duì)列空間的尾部已經(jīng)放置了元素，則下一個(gè)元素應(yīng)該旋轉(zhuǎn)到隊(duì)列空間的首部，即rear=1
退隊(duì)運(yùn)算：每退隊(duì)一個(gè)元素，排頭指針加1。當(dāng)排頭指針front=m+1時(shí)，即排頭指針指向隊(duì)列空間的尾部，退隊(duì)后，排頭指針指向隊(duì)列空間的開始，即front=1。
在隊(duì)列操作時(shí)，循環(huán)隊(duì)列滿時(shí)，front=rear，隊(duì)列空時(shí)，也有rear=front，即在隊(duì)列空或滿時(shí)，排頭指針和隊(duì)尾指針均指向同一個(gè)位置。要判斷隊(duì)列空或滿時(shí)，還應(yīng)增加一個(gè)標(biāo)志，s值的定義：
判斷隊(duì)列空與隊(duì)列滿的條件下：
隊(duì)列空的條件：s=0
隊(duì)列滿的條件：s=1、front=rear
（1）入隊(duì)運(yùn)算
即在隊(duì)尾加入一個(gè)新元素。這個(gè)運(yùn)算有兩個(gè)基本操作：首先，將隊(duì)尾指針加1，即rear=rear+1，當(dāng)rear=m+1時(shí)，置rear=1，然后，將新元素插入到隊(duì)尾指針指向的位置。
當(dāng)循環(huán)隊(duì)列非空（s=1），且front=rear時(shí)，隊(duì)列滿，不能進(jìn)行入隊(duì)操作。此情況稱“上溢”。
（2）退隊(duì)操作
即將隊(duì)首的元素賦給一個(gè)指定的變量。該運(yùn)算也有兩個(gè)基本操作：首先，將排頭指針加1，即front=front+1，當(dāng)front=m+1時(shí)，置front=1，然后，將排頭指針指向的元素賦給指定的變量。
當(dāng)循環(huán)隊(duì)列為空（s=0）時(shí)，不能進(jìn)行退隊(duì)運(yùn)算。此種情況稱為“下溢”。