淺談棧和隊列

淺談棧和隊列

摘要棧和隊列是常見的數(shù)據(jù)結(jié)構(gòu)，是兩種非常重要的線性結(jié)構(gòu)，也都是線性表，它們是操作受限的的線性表，有順序棧、鏈?zhǔn)綏?、鏈?zhǔn)疥犃泻脱h(huán)隊列等形式。從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊列是受限的線性表，棧和隊列的數(shù)據(jù)元素具有單一的前驅(qū)和后繼的線性關(guān)系。他們廣泛應(yīng)用在操作系統(tǒng)和編譯程序等各種軟件系統(tǒng)中。

論文提綱1棧12隊列23棧的隊列的應(yīng)用區(qū)別34棧和隊列的發(fā)展前景4結(jié)束引言

在對高級語言編寫的源程序進(jìn)行編譯時類似于表達(dá)式括號匹配問題就是用棧來解決的；計算機(jī)系統(tǒng)在處理子程序之間的調(diào)用關(guān)系是，用棧來保存處理執(zhí)行過程中的調(diào)用次序?，F(xiàn)實世界中有許多問題可以用隊列描述。例如，對顧客服務(wù)部門的工作往往是按照隊列方式進(jìn)行的，這類系統(tǒng)乘坐排隊系統(tǒng)。程序設(shè)計中，也經(jīng)常使用隊列記錄需按照先進(jìn)先出方式處理的數(shù)據(jù)，例如鍵盤緩沖區(qū)，操作系統(tǒng)中的作業(yè)調(diào)度等。返回到總目錄1棧1.1棧的概念棧（stack）是一種特殊的線性表。作為一個簡單的例子，可以把食堂里冼凈的一摞碗看作一個棧。在通常情況下，最先冼凈的碗總是放在最底下，后冼凈的碗總是摞在最頂上。而在使用時，卻是從頂上拿取，也就是說，后冼的先取用，后摞上的先取用。如果我們把冼凈的碗“摞上”稱為進(jìn)棧（壓棧），把“取用碗”稱為出棧（彈出），那么上例的特點(diǎn)是：后進(jìn)棧的先出棧。然而，摞起來的碗實際上是一個線性表，只不過“進(jìn)?！焙汀俺鰲！倍荚谧铐斏线M(jìn)行，或者說，元素的插入和刪除操作都是在線性表的一端進(jìn)行而已。棧是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的一端進(jìn)行。插入元素又稱為進(jìn)棧，刪除元素又稱為出棧。允許進(jìn)行插入和刪除操作的一端稱為棧頂（top），另一端稱為棧（bottom）。處于棧頂位置的數(shù)據(jù)元素稱為棧頂元素，處于棧底位置的數(shù)據(jù)元素稱為棧底元素。不含任何數(shù)據(jù)元素的棧稱為空棧。1.2棧的基本操作棧除了在棧頂進(jìn)行進(jìn)棧與出棧外，還有初始化、判空等操作，常用的基本操作有：（1）初始化棧InitStack(S)。其作用是構(gòu)造一個空棧S。（2）判斷棧空EmptyStack(S)。其作用是判斷是否是空棧，若棧S為空，則返回1；否則返回0。（3）進(jìn)棧Push(S,x)。其作用是當(dāng)棧不為滿時，將數(shù)據(jù)元素x插入棧S中，使其為棧S的棧頂元素。（4）出棧Pop(S,x)。其作用是當(dāng)棧S不為空時，將棧頂元素賦給x，并從棧S中刪除當(dāng)前棧頂元素。（5）取棧頂元素GetTop(S,x)。其作用是當(dāng)棧S不為空時，將棧頂元素賦給x并返回，操作結(jié)果只是讀取棧頂元素，棧S不發(fā)生變化。由于棧是操作受限制的線性表，因此與線性表類似，棧也有兩種存儲結(jié)構(gòu)，即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。1.3.1順序棧棧的順序存儲結(jié)構(gòu)稱為順序棧。類似于順序表的類型定義，順序棧是用一個預(yù)設(shè)的足夠長度的一維數(shù)組和一個記錄棧頂元素位置的變量來實現(xiàn)。1.3.2鏈棧用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的棧稱為鏈棧[3]，鏈棧與不帶頭結(jié)點(diǎn)單鏈表組織形式相似，因為棧的主要操作是在棧頂進(jìn)行插入與刪除操作，顯然將鏈表的第一個結(jié)點(diǎn)作為棧頂是最方便的，因此，沒有必要如單鏈表那樣為了操作方便附加一個頭結(jié)點(diǎn)。鏈棧的基本操作實現(xiàn)也有初始化棧操作，判斷棧空操作，進(jìn)棧操作，出棧操作，取棧頂元素。

。1.3棧的分類2.1隊列的概念在日常生活中的排隊上車，排隊的規(guī)則是不允許“插隊”。后來的人需站在隊尾，每次總是隊頭先上車。這種先進(jìn)先出的規(guī)則應(yīng)用在數(shù)據(jù)結(jié)構(gòu)中稱為隊列（queue），隊列又稱為先進(jìn)先出（firstinfirstout）的線性表，簡稱FIFO表。隊列也是一種特殊的線性表[4]。與棧不同，其插入操作限定在線性表的一端進(jìn)行，刪除操作限定在線性表的另一端進(jìn)行，隊列插入操作又稱為入隊，刪除操作又稱為出隊，允許進(jìn)行插入的一端稱為隊尾（rear），允許進(jìn)行刪除的一端稱為隊頭（front）。處于隊頭位置的數(shù)據(jù)元素稱為隊頭元素。處于隊尾位置的數(shù)據(jù)元素稱為隊尾元素。不含任何數(shù)據(jù)元素的隊列稱為空隊。2隊列2.2隊列的基本操作

隊列的除了在隊頭進(jìn)行出隊和隊尾進(jìn)行入隊外，還有初始化、判空等操作，常用的基本操作有：（1）初始化隊列InitQueue(Q)。其作用是構(gòu)造一個空隊列Q。（2）判斷隊列空EmptyQueue(Q)。其作用是判斷是否是空隊列，若隊列Q為空，則返回1；否則返回0。（3）入隊EnQueue(Q,x)。其作用是當(dāng)隊列不為滿時，將數(shù)據(jù)元素x插入隊列Q的隊尾，使其為隊列Q的隊尾元素。（4）出隊DeQueue(Q,x)。其作用是當(dāng)隊列Q不為空時，將隊頭元素賦給x，并從隊列Q中刪除當(dāng)前隊頭元素，而其后繼元素成為隊頭元素。（5）取隊頭元素GetFront(Q,x)。其作用是當(dāng)隊列Q不為空時，將隊頭元素賦給x并返回，操作結(jié)果只是讀取隊頭元素，隊列Q不發(fā)生變化。UGS由于隊列是操作受限制的線性表，因此與線性表類似，隊列也有兩種存儲結(jié)構(gòu)，即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。隊列的順序存儲結(jié)構(gòu)需要使用一個數(shù)組和兩個整型變量來實現(xiàn)，利用數(shù)組來順序存儲隊列中的所有元素，利用兩個整型變量來分別存儲隊首元素和隊尾元素的下標(biāo)位置，分別稱它們?yōu)殛犑字羔樅完犖仓羔槨?/p>

隊列也是操作受限的線性表。限定在隊尾處插入，而在隊頭處刪除。隊列是先進(jìn)先出（FirstInFirstOout，F(xiàn)IFO）的線性表。UGS

約定隊列的頭指針front指向隊列頭元素前一位置，而為指針rear指向隊尾元素自身。循環(huán)隊列是重要數(shù)據(jù)結(jié)構(gòu)，即指隊列的順序存儲結(jié)構(gòu)。凡涉及隊頭或隊尾指針的修改都要對MAXSIZE求模：front=(front+1)%MAXSIZE;rear=(rear+1)%MAXSIZE;

循環(huán)隊列，隊空的判定條件：rear==front；循環(huán)隊列，隊滿的的判定條件是：(rear+1)%MAXSIZE==front；

隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊列。通常設(shè)附加頭結(jié)點(diǎn)，并設(shè)隊頭指針指向頭結(jié)點(diǎn)，即指向第一個數(shù)據(jù)結(jié)點(diǎn)的前一位置。隊列的尾指針指向終端結(jié)點(diǎn)。鏈隊列的基本操作，也是單鏈表操作的簡化，插入只考慮在鏈隊列的尾部進(jìn)行，刪除只考慮在鏈隊列的頭部進(jìn)行，其時間復(fù)雜度均為O(1)。UGS1.隊列先進(jìn)先出，棧先進(jìn)后出。

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

3棧和隊列的應(yīng)用區(qū)別UGS3.遍歷數(shù)據(jù)速度不同。棧只能從頭部取數(shù)據(jù)也就最先放入的需要遍歷整個棧最后才能取出來，而且在遍歷數(shù)據(jù)的時候還得為數(shù)據(jù)開辟臨時空間，保持?jǐn)?shù)據(jù)在遍歷前的一致性隊列怎不同，他基于地址指針進(jìn)行遍歷，而且可以從頭或尾部開始遍歷，但不能同時遍歷，無需開辟臨時空間，因為在遍歷的過程中不影像數(shù)據(jù)結(jié)構(gòu)，速度要快的多。棧（Stack）是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。隊列（Queue）是限定只能在表的一端進(jìn)行插入和在另一端進(jìn)行刪除操作的線性表。從"數(shù)據(jù)結(jié)構(gòu)"的角度看，它們都是線性結(jié)構(gòu)，即數(shù)據(jù)元素之間的關(guān)系相同。但它們是完全不同的數(shù)據(jù)類型。除了它們各自的基本操作集不同外，主要區(qū)別是對插入和刪除操作的"限定"。棧和隊列是在程序設(shè)計中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，它們的特點(diǎn)在于基本操作的特殊性，棧必須按"后進(jìn)先出"的規(guī)則進(jìn)行操作，而隊列必須按"先進(jìn)先出"的規(guī)則進(jìn)行操作。和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結(jié)構(gòu)。UGS棧和隊列在各類系統(tǒng)中應(yīng)用廣泛。堆棧技術(shù)被廣泛應(yīng)用于編譯軟件和程序設(shè)計，操作系統(tǒng)、事務(wù)管理中廣泛應(yīng)用了隊列技術(shù)。討論堆棧與隊列的結(jié)構(gòu)特征與實現(xiàn)特點(diǎn)，有重要意義。

4棧和隊列的發(fā)展前景

UGS目前，國內(nèi)外關(guān)于數(shù)據(jù)結(jié)構(gòu)中棧和隊列這兩種