第3章　棧和隊列

 

3.1　復習筆記

一、棧

1棧的定義與基本操作

（1）棧的定義

棧是被限定僅在表尾進行插入或刪除操作的線性表。棧中數據元素同屬一種數據類型，數據元素之間呈線性關系。假設棧中有n個數據元素（a₁，a₂，…，a_n），則對每一個元素a_i（i＝1，2，…，n－1）都存在關系<a_i，a_i＋1>，并且a₁無前驅，a_n無后繼。

其中，表尾端稱為棧頂（top），表頭端稱為棧底（bottom），如圖3-1所示。不含元素的空表稱為空棧。棧的修改是按后進先出的原則進行的，因此，棧又稱為后進先出的線性表（簡稱LIFO結構）。

圖3-1　棧的示意圖

（2）棧的基本操作

①INISTACK(S)：初始化函數。

②EMPTY(S)：判棧空函數。

③PUSH(S,x)：入棧函數。

④POP(S)：出棧函數。

⑤GETTOP(S)：取棧頂元素函數。

⑥CLEAR(S)：棧置空操作。

⑦CURRENT-SIZE(S)：求當前棧中元素個數函數。

2棧的表示和實現

（1）順序棧

順序棧即棧的順序存儲結構，是利用一組地址連續的存儲單元依次存放自棧底到棧頂的數據元素，同時設指針top指示棧頂元素的當前位置。

棧滿：top＝arrmax時表棧滿，此時不能進行入棧操作。

棧空：top＝0時表棧空，此時不能進行出棧和取棧頂元素等操作。

【注意】共享棧是指兩個棧共享一個數組空間，也是順序棧的一種。它將兩個棧的棧底設置在數組的兩端（設top1＝－1，top2＝maxSize為棧空），入棧則分別向數組的中間位置靠近，若兩棧“相遇”（top2－top1＝1），則棧滿。

（2）鏈棧

采用鏈式存儲結構存儲的棧叫鏈棧。一個鏈棧由其棧頂指針唯一確定，且鏈棧一般不存在棧滿的情況。鏈棧如圖3-2所示。

圖3-2　鏈棧示意圖

二、棧的應用舉例

1括號匹配

括號匹配算法如下：

①初始化一個空棧，從表達式中順序讀入括號。

②當讀到左括號時進行入棧操作，且該左括號具有當前等待匹配的括號中最高的優先級。

③當讀到右括號時進行出棧操作，從棧頂取出具有最高優先級的括號，看是否與右括號相匹配。

當棧空且讀完表達式中所有括號，算法結束。

【注意】當表達式中出現了其他形式的括號時，匹配步驟不變。

2表達式求值

算符優先法（一種根據算術四則運算關系的規定來實現表達式求值的算法）算法如下：

①定義兩個棧，一個用于寄存運算符（OPTR棧），一個用于寄存操作數或者計算結果（OPND棧）。

②置操作數棧（OPND）為空，表達式起始符“#”為運算符棧（OPTR）的棧底元素。

③依次讀入表達式中的字符，若該字符為操作數，則進入OPND棧；若是運算符，則和OPTR棧頂運算符比較優先級，若該字符優先級低于OPTR棧頂元素優先級，則需將OPTR棧頂運算符代入相關運算后再進行入棧操作，反之直接入棧，直到求得結果（即OPTR棧頂元素和當前讀入字符均為“#”）。

【注意】如表3-1所示定義了算符之間的優先關系。

表3-1　算符間的優先關系

三、棧與遞歸的實現

1遞歸的定義

一個直接調用自身或通過一系列過程調用語句間接地調用自身的過程，稱做遞歸過程。

（1）分類

①直接遞歸

例如：

PROCENDURE A;

BEGIN

…

A;

…

END;

過程A中的語句直接調用了過程A本身，這叫做直接遞歸調用。

②間接遞歸

例如：

PROCENDURE B; PROCENDURE C;
BEGIN BEGIN
… …
C; B;
… …
END; END;

過程B中調用了過程C，而過程C又調用了過程B。這兩個過程都通過另一個過程間接調用了它們自身，這就叫做間接遞歸調用。

（2）優缺點

①優點：

能將原始問題轉換成屬性相同但規模較小的子問題，程序更加易讀，結構更加清晰。

②缺點：

遞歸程序時空復雜度一般比非遞歸程序高，運行效率也更低。

2棧在遞歸中的應用

棧一般被應用在遞歸程序轉換成非遞歸程序中，將原本由系統管理的遞歸過程改為程序員管理。在非遞歸程序中，棧有兩個作用：

（1）將本層遞歸調用時的實際參數和返回地址傳遞給下一層遞歸；

（2）保存本層參數和局部變量，從下一層返回本層時繼續恢復使用。

四、隊列

1隊列的定義與基本操作

（1）隊列的定義

隊列中數據元素同屬一種數據類型，數據元素之間呈線性關系。假設隊列中有n個數據元素（a₁，a₂，…，a_n），則對每一個元素a_i（i＝1，2，…，n－1）都存在關系（a_i，a_i＋1），并且a₁無前驅，a_n無后繼。

隊列是一種先進先出（FIFO）的線性表。它只允許在表的一端插入元素，而在另一端刪除元素。允許插入的一端叫做隊尾（rear），允許刪除的一端則稱為隊頭（front）。

【注意】特殊的隊列——雙端隊列

雙端隊列是限定插入和刪除操作在表的兩端進行的線性表，如圖3-3所示。雙端隊列能夠在端1和端2分別進行操作。其中，雙端隊列能夠根據實際情況對其進行限定，比如限定只允許端1進行插入，端1和端2均能進行刪除的雙端隊列。

圖3-3　雙端隊列

（2）隊列的基本操作

①INIQUEUE(Q)：初始化函數。

②EMPTY(Q)：判空函數。

③ENQUEUE(Q,x)：入隊列函數。

④DLQUEUE(Q)：出隊列函數。

⑤GETHEAD(Q)：取隊頭元素函數。

⑥CLEAR(Q)：隊列置空函數。

⑦CURRENT_SIZE(Q)：求隊列當前所含元素個數的函數。

2隊列的表示與實現

（1）隊列的順序存儲結構

①隊列的順序存儲

隊列的順序存儲是指分配一塊連續的存儲空間存儲隊列中的元素，并設立front指針指向隊頭位置，設立rear指針指向隊尾位置（一般front指向隊頭元素，rear指向隊尾元素的下一位置）。

②循環隊列

把存儲隊列元素的表從邏輯上看作一個環，即為循環隊列。它能夠避免一般順序存儲的隊列出現的“假溢出”（隊列在進行多次入隊和出隊操作后導致存儲空間剩余而無法繼續入隊）現象。

【注意】循環隊列相關操作

設隊列為Q，循環隊列中入隊出隊需借助取余運算，具體如下：

初始狀態：Q.front=Q.rear=0;

隊首指針進1：Q.front=(Q.front+1)%MAXSIZE;

隊尾指針進1：Q.rear=(Q.rear+1)%MAXSIZE;

隊列長度：(Q.rear-Q.front+MAXSIZE)%MAXSIZE;

隊滿條件：(Q.rear+1)%MAXSIZE==Q.front;

隊空條件：Q.front==Q.rear;

（2）隊列的鏈式存儲結構

用鏈表表示的隊列簡稱為鏈隊列，如圖3-4所示。一個鏈隊列有兩個分別指示隊頭和隊尾的指針（分別稱為頭指針和尾指針）。

圖3-4　鏈隊列示意圖

【注意】為了操作方便，通常給鏈隊列添加一個頭結點，并令頭指針指向頭結點。鏈隊列判空條件為頭指針和尾指針均指向頭結點。

五、離散事件模擬