淺談棧和隊列

1、淺談棧和隊列 1234 引言引言 在對高級語言編寫的源程序進(jìn)行編譯時在對高級語言編寫的源程序進(jìn)行編譯時類似于表達(dá)式括號匹配問題就是用棧來解決類似于表達(dá)式括號匹配問題就是用棧來解決的；計算機(jī)系統(tǒng)在處理子程序之間的調(diào)用關(guān)的；計算機(jī)系統(tǒng)在處理子程序之間的調(diào)用關(guān)系是，用棧來保存處理執(zhí)行過程中的調(diào)用次系是，用棧來保存處理執(zhí)行過程中的調(diào)用次序?，F(xiàn)實(shí)世界中有許多問題可以用隊列描述。序?，F(xiàn)實(shí)世界中有許多問題可以用隊列描述。例如，對顧客服務(wù)部門的工作往往是按照隊例如，對顧客服務(wù)部門的工作往往是按照隊列方式進(jìn)行的，這類系統(tǒng)乘坐排隊系統(tǒng)。程列方式進(jìn)行的，這類系統(tǒng)乘坐排隊系統(tǒng)。程序設(shè)計中，也經(jīng)常使用隊列記錄需按照先進(jìn)

2、序設(shè)計中，也經(jīng)常使用隊列記錄需按照先進(jìn)先出方式處理的數(shù)據(jù)，例如鍵盤緩沖區(qū)，操先出方式處理的數(shù)據(jù)，例如鍵盤緩沖區(qū)，操作系統(tǒng)中的作業(yè)調(diào)度等。作系統(tǒng)中的作業(yè)調(diào)度等。1 棧棧1.1 棧的概念棧的概念 棧（棧（stack）是一種特殊的線性表。作為一個）是一種特殊的線性表。作為一個簡單的例子，可以把食堂里冼凈的一摞碗看作一個簡單的例子，可以把食堂里冼凈的一摞碗看作一個棧。在通常情況下，最先冼凈的碗總是放在最底下，棧。在通常情況下，最先冼凈的碗總是放在最底下，后冼凈的碗總是摞在最頂上。而在使用時，卻是從后冼凈的碗總是摞在最頂上。而在使用時，卻是從頂上拿取，也就是說，后冼的先取用，后摞上的先頂上拿取，也就是說

3、，后冼的先取用，后摞上的先取用。如果我們把冼凈的碗取用。如果我們把冼凈的碗“摞上摞上”稱為進(jìn)棧（壓稱為進(jìn)棧（壓棧），把棧），把“取用碗取用碗”稱為出棧（彈出），那么上例稱為出棧（彈出），那么上例的特點(diǎn)是：后進(jìn)棧的先出棧。然而，摞起來的碗實(shí)的特點(diǎn)是：后進(jìn)棧的先出棧。然而，摞起來的碗實(shí)際上是一個線性表，只不過際上是一個線性表，只不過“進(jìn)棧進(jìn)?！焙秃汀俺鰲３鰲！倍级荚谧铐斏线M(jìn)行，或者說，元素的插入和刪除操作都在最頂上進(jìn)行，或者說，元素的插入和刪除操作都是在線性表的一端進(jìn)行而已。是在線性表的一端進(jìn)行而已。 棧是一種特殊的線性表。其特殊性在于棧是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作

4、只能在線性限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的一端進(jìn)行。表的一端進(jìn)行。 插入元素又稱為進(jìn)棧，刪除元素又稱為插入元素又稱為進(jìn)棧，刪除元素又稱為出棧。允許進(jìn)行插入和刪除操作的一端稱為出棧。允許進(jìn)行插入和刪除操作的一端稱為棧頂（棧頂（top），另一端稱為棧（），另一端稱為棧（bottom）。）。處于棧頂位置的數(shù)據(jù)元素稱為棧頂元素，處處于棧頂位置的數(shù)據(jù)元素稱為棧頂元素，處于棧底位置的數(shù)據(jù)元素稱為棧底元素。不含于棧底位置的數(shù)據(jù)元素稱為棧底元素。不含任何數(shù)據(jù)元素的棧稱為空棧。任何數(shù)據(jù)元素的棧稱為空棧。 1.2棧的基本操作棧的基本操作 棧除了在棧頂進(jìn)行進(jìn)棧與出棧外，還有初始化、棧除了在棧頂進(jìn)行進(jìn)棧與出

5、棧外，還有初始化、判空等操作，常用的基本操作有：判空等操作，常用的基本操作有：（1）初始化棧）初始化棧InitStack(S)。其作用是構(gòu)造一個空。其作用是構(gòu)造一個空棧棧S。（2）判斷棧空）判斷?？誆mptyStack(S)。其作用是判斷是。其作用是判斷是否是空棧，若棧否是空棧，若棧S為空，則返回為空，則返回1；否則返回；否則返回0。（3）進(jìn)棧）進(jìn)棧Push(S,x)。其作用是當(dāng)棧不為滿時，將。其作用是當(dāng)棧不為滿時，將數(shù)據(jù)元素數(shù)據(jù)元素x插入棧插入棧S中，使其為棧中，使其為棧S的棧頂元素。的棧頂元素。（4）出棧）出棧Pop(S,x)。其作用是當(dāng)棧。其作用是當(dāng)棧S不為空時，將不為空時，將棧頂元素賦

6、給棧頂元素賦給x，并從棧，并從棧S中刪除當(dāng)前棧頂元素。中刪除當(dāng)前棧頂元素。（5）取棧頂元素）取棧頂元素GetTop(S,x)。其作用是當(dāng)棧。其作用是當(dāng)棧S不不為空時，將棧頂元素賦給為空時，將棧頂元素賦給x并返回，操作結(jié)果只是讀并返回，操作結(jié)果只是讀取棧頂元素，棧取棧頂元素，棧S不發(fā)生變化。不發(fā)生變化。 由于棧是操作受限制的線性表，因此與線性表類似，棧也有兩種由于棧是操作受限制的線性表，因此與線性表類似，棧也有兩種存儲結(jié)構(gòu)，即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。存儲結(jié)構(gòu)，即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。1.3.11.3.1順序棧順序棧 棧的順序存儲結(jié)構(gòu)稱為順序棧。類似于順序表的類型定義，順序棧棧的順序存儲

7、結(jié)構(gòu)稱為順序棧。類似于順序表的類型定義，順序棧是用一個預(yù)設(shè)的足夠長度的一維數(shù)組和一個記錄棧頂元素位置的變量是用一個預(yù)設(shè)的足夠長度的一維數(shù)組和一個記錄棧頂元素位置的變量來實(shí)現(xiàn)。來實(shí)現(xiàn)。 1.3.21.3.2鏈棧鏈棧 用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)的棧稱為鏈棧用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)的棧稱為鏈棧33，鏈棧與不帶頭結(jié)點(diǎn)單鏈表，鏈棧與不帶頭結(jié)點(diǎn)單鏈表組織形式相似，因?yàn)闂５闹饕僮魇窃跅ｍ斶M(jìn)行插入與刪除操作，顯組織形式相似，因?yàn)闂５闹饕僮魇窃跅ｍ斶M(jìn)行插入與刪除操作，顯然將鏈表的第一個結(jié)點(diǎn)作為棧頂是最方便的，因此，沒有必要如單鏈然將鏈表的第一個結(jié)點(diǎn)作為棧頂是最方便的，因此，沒有必要如單鏈表那樣為了操作方便附加一個頭結(jié)點(diǎn)。

8、表那樣為了操作方便附加一個頭結(jié)點(diǎn)。 鏈棧的基本操作實(shí)現(xiàn)也有初始化棧操作，判斷?？詹僮鳎M(jìn)棧操作，鏈棧的基本操作實(shí)現(xiàn)也有初始化棧操作，判斷?？詹僮?，進(jìn)棧操作，出棧操作，取棧頂元素。出棧操作，取棧頂元素。 。 1.3棧的分類棧的分類 2.1 2.1 隊列的概念隊列的概念 在日常生活中的排隊上車，排隊的規(guī)則是不允許在日常生活中的排隊上車，排隊的規(guī)則是不允許“插插隊隊”。后來的人需站在隊尾，每次總是隊頭先上車。這。后來的人需站在隊尾，每次總是隊頭先上車。這種先進(jìn)先出的規(guī)則應(yīng)用在數(shù)據(jù)結(jié)構(gòu)中稱為隊列（種先進(jìn)先出的規(guī)則應(yīng)用在數(shù)據(jù)結(jié)構(gòu)中稱為隊列（queuequeue），），隊列又稱為先進(jìn)先出（隊列又稱為先進(jìn)先

9、出（first in first outfirst in first out）的線性表，）的線性表，簡稱簡稱FIFOFIFO表。表。 隊列也是一種特殊的線性表隊列也是一種特殊的線性表44。與棧不同，其插入操作。與棧不同，其插入操作限定在線性表的一端進(jìn)行，刪除操作限定在線性表的另限定在線性表的一端進(jìn)行，刪除操作限定在線性表的另一端進(jìn)行，隊列插入操作又稱為入隊，刪除操作又稱為一端進(jìn)行，隊列插入操作又稱為入隊，刪除操作又稱為出隊，允許進(jìn)行插入的一端稱為隊尾（出隊，允許進(jìn)行插入的一端稱為隊尾（rearrear），允許進(jìn)），允許進(jìn)行刪除的一端稱為隊頭（行刪除的一端稱為隊頭（frontfront）。處于隊

10、頭位置的數(shù)據(jù)）。處于隊頭位置的數(shù)據(jù)元素稱為隊頭元素。處于隊尾位置的數(shù)據(jù)元素稱為隊尾元素稱為隊頭元素。處于隊尾位置的數(shù)據(jù)元素稱為隊尾元素。不含任何數(shù)據(jù)元素的隊列稱為空隊元素。不含任何數(shù)據(jù)元素的隊列稱為空隊。2隊列隊列2.2 隊列的基本操作隊列的基本操作 隊列的除了在隊頭進(jìn)行出隊和隊尾進(jìn)行入隊外，還有初始化、隊列的除了在隊頭進(jìn)行出隊和隊尾進(jìn)行入隊外，還有初始化、判空等操作，常用的基本操作有：判空等操作，常用的基本操作有：（1）初始化隊列）初始化隊列InitQueue(Q)。其作用是構(gòu)造一個空隊列。其作用是構(gòu)造一個空隊列Q。（2）判斷隊列空）判斷隊列空EmptyQueue(Q)。其作用是判斷是否是空

11、隊列，。其作用是判斷是否是空隊列，若隊列若隊列Q為空，則返回為空，則返回1；否則返回；否則返回0。（3）入隊）入隊EnQueue(Q,x)。其作用是當(dāng)隊列不為滿時，將數(shù)據(jù)元。其作用是當(dāng)隊列不為滿時，將數(shù)據(jù)元素素x插入隊列插入隊列Q的隊尾，使其為隊列的隊尾，使其為隊列Q的隊尾元素。的隊尾元素。（4）出隊）出隊DeQueue(Q,x)。其作用是當(dāng)隊列。其作用是當(dāng)隊列Q不為空時，將隊頭不為空時，將隊頭元素賦給元素賦給x，并從隊列，并從隊列Q中刪除當(dāng)前隊頭元素，而其后繼元素成為中刪除當(dāng)前隊頭元素，而其后繼元素成為隊頭元素。隊頭元素。（5）取隊頭元素）取隊頭元素GetFront(Q,x)。其作用是當(dāng)隊列

12、。其作用是當(dāng)隊列Q不為空時，不為空時，將隊頭元素賦給將隊頭元素賦給x并返回，操作結(jié)果只是讀取隊頭元素，隊列并返回，操作結(jié)果只是讀取隊頭元素，隊列Q不不發(fā)生變化。發(fā)生變化。 由于隊列是操作受限制的線性表，因此與線性表類由于隊列是操作受限制的線性表，因此與線性表類似，隊列也有兩種存儲結(jié)構(gòu)，即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱嫠?，隊列也有兩種存儲結(jié)構(gòu)，即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。儲結(jié)構(gòu)。 隊列的順序存儲結(jié)構(gòu)需要使用一個數(shù)組和兩個整型隊列的順序存儲結(jié)構(gòu)需要使用一個數(shù)組和兩個整型變量來實(shí)現(xiàn)，利用數(shù)組來順序存儲隊列中的所有元素，變量來實(shí)現(xiàn)，利用數(shù)組來順序存儲隊列中的所有元素，利用兩個整型變量來分別存儲隊首元素和隊尾元

13、素的下利用兩個整型變量來分別存儲隊首元素和隊尾元素的下標(biāo)位置，分別稱它們?yōu)殛犑字羔樅完犖仓羔?。?biāo)位置，分別稱它們?yōu)殛犑字羔樅完犖仓羔槨?隊列也是操作受限的線性表。限定在隊尾處插入，隊列也是操作受限的線性表。限定在隊尾處插入，而在隊頭處刪除。而在隊頭處刪除。 隊列是先進(jìn)先出（隊列是先進(jìn)先出（First In First Oout，F(xiàn)IFO）的線性表。的線性表。 約定隊列的頭指針約定隊列的頭指針front指向隊列頭元素前一位置，而為指針指向隊列頭元素前一位置，而為指針rear指向隊尾元素自身。循環(huán)隊列是重要數(shù)據(jù)結(jié)構(gòu)，即指隊列的指向隊尾元素自身。循環(huán)隊列是重要數(shù)據(jù)結(jié)構(gòu)，即指隊列的順序存儲結(jié)構(gòu)。凡涉及

14、隊頭或隊尾指針的修改都要對順序存儲結(jié)構(gòu)。凡涉及隊頭或隊尾指針的修改都要對MAXSIZE求模：求模： front=(front+1) % MAXSIZE; rear=(rear+1) % MAXSIZE; 循環(huán)隊列，隊空的判定條件：循環(huán)隊列，隊空的判定條件：rear=front； 循環(huán)隊列，隊滿的的判定條件是：循環(huán)隊列，隊滿的的判定條件是：(rear+1)%MAXSIZE=front； 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊列。通常設(shè)附加頭結(jié)點(diǎn)，并設(shè)隊隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊列。通常設(shè)附加頭結(jié)點(diǎn)，并設(shè)隊頭指針指向頭結(jié)點(diǎn)，即指向第一個數(shù)據(jù)結(jié)點(diǎn)的前一位置。隊列的尾頭指針指向頭結(jié)點(diǎn)，即指向第一個數(shù)據(jù)結(jié)點(diǎn)的前一位

15、置。隊列的尾指針指向終端結(jié)點(diǎn)。指針指向終端結(jié)點(diǎn)。 鏈隊列的基本操作，也是單鏈表操作的簡化，插入只考慮在鏈隊鏈隊列的基本操作，也是單鏈表操作的簡化，插入只考慮在鏈隊列的尾部進(jìn)行，刪除只考慮在鏈隊列的頭部進(jìn)行，其時間復(fù)雜度均列的尾部進(jìn)行，刪除只考慮在鏈隊列的頭部進(jìn)行，其時間復(fù)雜度均為為O(1)。1. 1. 隊列先進(jìn)先出，棧先進(jìn)后出。隊列先進(jìn)先出，棧先進(jìn)后出。 2. 2. 對插入和刪除操作的對插入和刪除操作的 限定限定 。 棧是限定只能在表的棧是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。一端進(jìn)行插入和刪除操作的線性表。 隊列是限定只能隊列是限定只能在表的一端進(jìn)行插入和在另一端進(jìn)行刪除操作的線性表

16、。在表的一端進(jìn)行插入和在另一端進(jìn)行刪除操作的線性表。從從 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 的角度看，它們都是線性結(jié)構(gòu)，即數(shù)據(jù)元的角度看，它們都是線性結(jié)構(gòu)，即數(shù)據(jù)元素之間的關(guān)系相同。但它們是完全不同的數(shù)據(jù)類型。除素之間的關(guān)系相同。但它們是完全不同的數(shù)據(jù)類型。除了它們各自的基本操作集不同外，主要區(qū)別是對插入和了它們各自的基本操作集不同外，主要區(qū)別是對插入和刪除操作的刪除操作的 限定限定 。棧和隊列是在程序設(shè)計中被廣泛使。棧和隊列是在程序設(shè)計中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，它們的特點(diǎn)在于基本操作的特用的兩種線性數(shù)據(jù)結(jié)構(gòu)，它們的特點(diǎn)在于基本操作的特殊性，棧必須按殊性，棧必須按 后進(jìn)先出后進(jìn)先出 的規(guī)則進(jìn)行操作，而隊

17、列必的規(guī)則進(jìn)行操作，而隊列必須按須按 先進(jìn)先出先進(jìn)先出 的規(guī)則進(jìn)行操作。和線性表相比，它的規(guī)則進(jìn)行操作。和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結(jié)構(gòu)。定性的線性表結(jié)構(gòu)。 3棧和隊列的應(yīng)用區(qū)別棧和隊列的應(yīng)用區(qū)別 3. 3. 遍歷數(shù)據(jù)速度不同。棧只能從頭部取數(shù)據(jù)遍歷數(shù)據(jù)速度不同。棧只能從頭部取數(shù)據(jù) 也就最先放入的需也就最先放入的需要遍歷整個棧最后才能取出來，而且在遍歷數(shù)據(jù)的時候還得為數(shù)據(jù)要遍歷整個棧最后才能取出來，而且在遍歷數(shù)據(jù)的時候還得為數(shù)據(jù)開辟臨時空間，保持?jǐn)?shù)據(jù)在遍歷前的一致性隊列怎不同，他基于地開辟臨時空間，

18、保持?jǐn)?shù)據(jù)在遍歷前的一致性隊列怎不同，他基于地址指針進(jìn)行遍歷，而且可以從頭或尾部開始遍歷，但不能同時遍歷，址指針進(jìn)行遍歷，而且可以從頭或尾部開始遍歷，但不能同時遍歷，無需開辟臨時空間，因?yàn)樵诒闅v的過程中不影像數(shù)據(jù)結(jié)構(gòu)，速度要無需開辟臨時空間，因?yàn)樵诒闅v的過程中不影像數(shù)據(jù)結(jié)構(gòu)，速度要快的多。棧（快的多。棧（StackStack）是限定只能在表的一端進(jìn)行插入和刪除操作）是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。隊列（的線性表。隊列（QueueQueue）是限定只能在表的一端進(jìn)行插入和在另）是限定只能在表的一端進(jìn)行插入和在另一端進(jìn)行刪除操作的線性表。從一端進(jìn)行刪除操作的線性表。從 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)

19、構(gòu) 的角度看，它們都是的角度看，它們都是線性結(jié)構(gòu)，即數(shù)據(jù)元素之間的關(guān)系相同。但它們是完全不同的數(shù)據(jù)線性結(jié)構(gòu)，即數(shù)據(jù)元素之間的關(guān)系相同。但它們是完全不同的數(shù)據(jù)類型。除了它們各自的基本操作集不同外，主要區(qū)別是對插入和刪類型。除了它們各自的基本操作集不同外，主要區(qū)別是對插入和刪除操作的除操作的 限定限定 。棧和隊列是在程序設(shè)計中被廣泛使用的兩種線。棧和隊列是在程序設(shè)計中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，它們的特點(diǎn)在于基本操作的特殊性，棧必須按性數(shù)據(jù)結(jié)構(gòu)，它們的特點(diǎn)在于基本操作的特殊性，棧必須按 后進(jìn)后進(jìn)先出先出 的規(guī)則進(jìn)行操作，而隊列必須按的規(guī)則進(jìn)行操作，而隊列必須按 先進(jìn)先出先進(jìn)先出 的規(guī)則進(jìn)行操作。的規(guī)則進(jìn)行操作。和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結(jié)構(gòu)稱為限定性的線性表結(jié)構(gòu)。 棧和隊列在各類系統(tǒng)中應(yīng)用廣泛。堆棧技棧和隊列在各類系統(tǒng)中應(yīng)用廣泛。堆棧技術(shù)被廣泛應(yīng)用于編譯軟件和程序設(shè)計，操作系術(shù)被廣泛應(yīng)用于編譯軟件和程序設(shè)計，操