1.1.3 棧和隊列

棧和隊列都是特殊的線性表，其定義符合線性表的定義，其操作也類似于線性表的操作，只不過增加了一些限定而已。

1.棧的定義與操作

棧（Stack）是一種特殊的線性表。棧是只能在表的一端進行插入和刪除運算的線性表。通常稱插入、刪除的這一端為棧頂（Top），另一端為棧底（Bottom），如圖1-2所示。當表中沒有元素時稱為空棧。棧頂元素總是后插入的元素，也是最先被刪除的元素；棧底元素總是最先被插入的元素，也是最后才能被刪除的元素。

假設棧S=（al,a2,a3,…,an），則a1為棧底元素，an為棧頂元素。棧中元素按a1,a2,a3,…,an的次序進棧，退棧的第一個元素應為棧頂元素，換句話說，棧的修改是按后進先出的原則進行的。因此，棧稱為先進后出表（First In Last Out，FILO），或后進先出表（Last In First Out，LIFO）。

棧的操作主要有入棧運算、退棧運算（出棧）和讀棧頂元素。

1）入棧運算：入棧運算是指在棧頂位置插入一個新元素。首先將棧頂指針加1（即Top加1），然后將元素插入到棧頂指針指向的位置。當棧頂指針已經指向存儲空間的最后一個位置時，說明棧空間已滿，不能再進行入棧操作，這種情況稱為棧“上溢”錯誤。

2）退棧運算：退棧是指取出棧頂元素并賦給一個指定的變量。首先將棧頂元素（棧頂指針指向的元素）賦給一個指定的變量，然后將棧頂指針減1（即Top減1）。當棧頂指針為0時，說明棧空，不可進行退棧操作，這種情況稱為棧的“下溢”錯誤。

3）讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個指定的變量。這個運算不刪除棧頂元素，只是將它賦給一個變量，因此棧頂指針不會改變。當棧頂指針為0時，說明棧空，讀不到棧頂元素。

2.隊列的定義與操作

隊列（Queue）是只允許在一端刪除、在另一端插入的順序表。允許刪除的一端叫作隊頭（Front），允許插入的一端叫作隊尾（Rear），如圖1-3所示。

（1）隊列的運算

當隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素a1,a2,…,an之后，a1是隊頭元素，an是隊尾元素。顯然退出隊列的次序也只能是a1,a2,…,an，也就是說隊列的修改是按先進先出的原則進行的。因此隊列亦稱為先進先出的線性表，或后進后出的線性表。

1）入隊操作：往隊列隊尾插入一個元素稱為入隊運算。

2）出隊操作：從隊列隊頭刪除一個元素稱為出隊運算。

（2）循環隊列的運算

所謂循環隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環狀空間。

在循環隊列中，用隊尾指針Rear指向隊列中的隊尾元素，用隊頭指針Front指向排頭元素的前一個位置。因此，從排頭指針Front指向的后一個位置直到隊尾指針Rear指向的位置之間的所有元素均為隊列中的元素。

在循環隊列中進行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。只不過當頭尾指針指向向量上界（Queuesize-l）時，其加1操作的結果是指向向量的下界0。

由于入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。因此，我們無法通過Front=Rear來判斷隊列是空還是滿。在實際使用循環隊列時，為了能區分隊列滿還是隊列空，通常還需增加一個標志值，其定義如下：當s=0時表示隊列空，當s=1時表示隊列非空。

入隊運算：入隊運算是指在循環隊列的隊尾加入一個新元素。首先將隊尾指針進1（即Rear=Rear+1），且當Rear=m+l時置Rear=1；然后將新元素插入到隊尾指針指向的位置。當循環隊列非空（s=l）且隊尾指針等于隊頭指針時，說明循環隊列已滿，不能進行入隊運算，這種情況稱為“上溢”。

出隊運算：出隊運算是指在循環隊列的隊頭位置退出一個元素并賦給指定的變量。首先將隊頭指針進1（即From=Front+1），且當Front=m+1時置Front=1，然后將排頭指針指向的元素賦給指定的變量。當循環隊列為空（s=0）時，不能進行出隊運算，這種情況稱為“下溢”。