小結

本章介紹了兩種特殊的線性表：棧和隊列。棧是插入和刪除操作限制在表尾一端進行，無論是在棧中插入數據元素還是刪除棧中數據元素，都只能固定在線性表的表尾進行。通常將進行插入和刪除操作的這一端稱為“棧頂”，而另一端稱為“棧底”。它是一種具有“后進先出”或“先進后出”特性的線性表。隊列是插入操作只限制在表尾進行，而刪除操作只限制在表頭進行。通常將允許進行插入操作的一端稱為“隊尾”，而將允許進行刪除操作的另一端稱為“隊首”。它是一種具有“先進先出”或“后進后出”的線性表。

棧的基本操作主要包括判棧是否為空、出棧、入棧和取棧頂元素等。隊列的基本操作主要包括判隊列是否為空、出隊、入隊和取隊首元素等。這些操作的時間復雜度都是O（1）。

棧與隊列都可用順序和鏈式兩種存儲方式加以實現，為此有順序棧和鏈棧、順序隊列和鏈隊列之分。其中：順序棧和順序隊列用數組實現；鏈棧和鏈隊列則用單鏈表進行存儲。讀者要注意的是，鏈棧結點中指針的指向是從棧頂開始依次向后鏈接的，也就是說鏈棧中結點的指針不像單鏈表那樣是指向它在線性表中的后繼，而是指向其在線性表中的前驅。鏈隊列結點的鏈接方向與單鏈表相同，但為了便于實現插入和刪除操作，鏈隊列除了引進一個隊首指針外，還引進了隊尾指針來指向隊尾元素，并將兩者組合形成一個隊列結構類型。

順序棧比鏈棧的使用更為廣泛。在順序棧中，注意掌握入棧和出棧操作，特別是在入棧操作前要進行的判滿條件和在出棧操作前要進行的判空條件。在鏈棧中的操作與單鏈表操作類似，而且由于入棧與出棧操作都是固定在鏈棧的棧頂位置進行，所以實現起來比單鏈表相應操作更為簡單。

循環隊列比非循環隊列使用更為廣泛。在順序存儲方式下，也要注意掌握隊列的入隊和出隊操作、隊列判空與判滿的條件，以及隊列“假溢出”的處理方法。循環順序隊列就是為了避免“假溢出”現象而提出的一種隊列。它是一個假想的環，是通過取模運算來使其首尾相連。特別要注意的是，在循環順序隊列中的入隊和出隊操作實現與在非循環順序隊列中的入隊和出隊操作實現的不同點在于，隊首和隊尾指針的變化不再是簡單的加1或減1，而需加1或減1后再做取模運算。在循環順序隊列中為了區分隊列的判空和判滿條件，特別提出了三種解決方法：第一種是少用一個存儲單元；第二種是設置一個標志變量；第三種是設置一個計數變量。鏈隊列中的操作也與單鏈表中的操作類似，而且由于入隊操作總是固定在鏈隊列的隊尾進行，而出隊操作總是固定在鏈隊列的隊首進行，所以鏈隊列的入隊和出隊操作實現起來非常簡單。

棧與隊列是兩種十分重要的，并且應用非常廣泛的數據結構。常見的棧的應用包括分隔符匹配問題的求解，表達式的轉換和求值，函數調用和遞歸實現和深度優先搜索遍歷等。凡是遇到對數據元素的讀取順序與處理順序相反，都可考慮使用棧將讀取到而又未處理的數據元素保存在棧中。常見的隊列的應用包括計算機系統中各種資源的管理，消息緩沖器的管理和廣度優先搜索遍歷等。凡是遇到對數據元素的讀取順序與處理順序相同，都可考慮使用隊列來保存讀取到而未處理的數據元素。

優先級隊列是帶有優先級的隊列。優先級隊列中的每一個數據元素都有一個優先權。優先權可以比較大小，它既可以在數據元素被插入優先級隊列時被人為賦予，也可以是數據元素本身所具有的某一屬性。優先權的大小決定著該對象接受服務的先后順序，所以也將其稱為優先級。優先級隊列不同于一般的隊列，它是按照數據元素優先級的高低來決定出隊的次序，而不是按照數據元素進入隊列的次序來決定的。一般隊列也可以被看作是一種特殊的優先級隊列。在一般隊列中，數據元素的優先級由其進入隊列的時間確定，時間越長，優先級越高。優先級隊列的實現方法可以采用有序、無序線性表或堆來實現。本章只介紹了在有序線性表上實現的優先級隊列。在這種情況下，入隊操作是進行數據元素的有序插入，即將待插入的數據元素插入隊列中的適當位置，并使插入后的隊列仍按照優先級從大到小的順序排放，入隊操作的時間復雜度為O（n）。出隊操作只要將隊首元素（即優先級最高的元素）從隊列中刪除即可，其時間復雜度為O（1）。在一些實際應用中，若需要采用一種數據結構來存儲數據元素，對這種數據結構的要求是：數據元素加入的次序是無關緊要的，但每次取出的數據元素應是具有最高優先級的數據元素，這時就可以采用優先級隊列來解決問題。

其實利用棧和隊列的思想還可以設計出其他一些變種的棧和隊列結構。例如雙端隊列，雙端棧等，這些都是根據插入與刪除操作位置受限的不相同而得名的。雙端隊列是指插入和刪除操作限制在線性表的兩端進行；雙端棧是指兩個底部相連的棧，它是一種添加限制的雙端隊列，并且規定從一端插入的數據元素只能從這一端刪除。這些變種的棧和隊列在某些特定情況下具有很好的應用價值。