1.5.2　棧與隊(duì)列

棧與隊(duì)列是另外兩種重要的線性結(jié)構(gòu)，它們可以使用上面所講的順序表或者鏈表的結(jié)構(gòu)來最終實(shí)現(xiàn)。

1．棧

棧可看成一種“特殊”的線性表，該線性表限定僅在表尾進(jìn)行插入和刪除操作。棧主要應(yīng)用于表達(dá)式的計(jì)算、子程序嵌套調(diào)用、遞歸調(diào)用等。

棧具有下述特殊的性質(zhì)：

（1）通常稱插入、刪除的這一端為棧頂（Top）；另一端稱為棧底（Bottom）。

（2）當(dāng)表中沒有元素時稱為空棧。

（3）棧的修改是按“后進(jìn)先出”的原則進(jìn)行，因此棧簡稱為LIFO（Last In First Out）表。每次刪除（退棧）的總是當(dāng)前棧中“最新”的元素，即最后插入（進(jìn)棧）的元素，而最先插入的元素是被放在棧的底部，要到最后才能刪除。

棧的示意圖如圖1-5所示。

和線性表類似，棧也有兩種存儲表示方法，即順序棧和鏈棧。順序棧指的是棧的順序存儲結(jié)構(gòu)，是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。設(shè)置棧頂指針為top，它指示棧頂元素在順序棧中的位置；棧底指針為base，它始終指向棧底的位置。初始時，top指向棧底，每當(dāng)插入一個元素時，top++；刪除棧頂元素時，top--，因此，非空棧中的top始終在棧頂元素的下一個位置。

鏈棧的定義和操作與鏈表類似，易于實(shí)現(xiàn)，不再贅述。

2．隊(duì)列

和棧相反，隊(duì)列是一種先進(jìn)先出（First In First Out，F(xiàn)IFO）的線性表，它只允許在表的一端進(jìn)行插入元素，而在另一端刪除元素。

隊(duì)列有下述特殊性質(zhì)：

（1）允許刪除的一端稱為隊(duì)頭（Front）。

（2）允許插入的一端稱為隊(duì)尾（Rear）。

（3）當(dāng)隊(duì)列中沒有元素時稱為空隊(duì)列。

（4）隊(duì)列的結(jié)構(gòu)特點(diǎn)是先進(jìn)隊(duì)的元素先出隊(duì)。假設(shè)有隊(duì)列Q=（a₁，a₂，…，a_n），則隊(duì)列Q中的元素是按a₁，a₂，…，a_n的次序進(jìn)隊(duì)，而第一個出隊(duì)的應(yīng)該是a₁，第二個出隊(duì)的應(yīng)該是a₂，只有在a_i-1出隊(duì)后，a_i才可以出隊(duì)（1≤i≤n）。

（5）隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。新來的成員總是加入隊(duì)尾（即不允許“加塞”），每次離開的成員總是隊(duì)頭元素，即當(dāng)前“最老的”成員，而不允許中途離隊(duì)。

隊(duì)列的示意圖如圖1-6所示。

和線性表類似，隊(duì)列也有兩種存儲結(jié)構(gòu)，即順序存儲結(jié)構(gòu)（循環(huán)隊(duì)列）和鏈?zhǔn)酱鎯Y(jié)構(gòu)（鏈隊(duì)列）。

和順序棧類似，在隊(duì)列的順序存儲結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲單元依次存放從隊(duì)頭到隊(duì)尾的元素之外，尚需設(shè)置兩個指針front和rear，它們分別指示隊(duì)列的頭元素和尾元素。初始時，令front=rear=0，每當(dāng)插入1個新的元素，rear增加1；每當(dāng)刪除1個新的元素，front增加1；當(dāng)front=rear時，隊(duì)列為空。這種操作方式會導(dǎo)致一個新的情況：如果插入和刪除的元素越來越多，rear的值將一直增加，最終達(dá)到所分配存儲單元的最大值，當(dāng)要繼續(xù)插入新的元素時，隊(duì)尾已沒有空間了。但如果front>0，此時第0個單元至第front-1個單元的存儲空間并未占用。那么，該如何利用這部分可用空間呢？一個較為巧妙的辦法是將順序隊(duì)列構(gòu)造為一個環(huán)狀的空間，稱為循環(huán)隊(duì)列。這樣，空間就可以循環(huán)利用了。

在一個鏈隊(duì)列中，需要兩個分別指示隊(duì)頭和隊(duì)尾的指針才能唯一確定，其操作即為線性鏈表的插入和刪除操作的特殊情況，只是尚需修改隊(duì)尾指針或隊(duì)頭指針。