淺談棧和隊(duì)列

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

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

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

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

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

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

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

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

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

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

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

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

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