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