淺談棧和隊列的應用

1、淺談棧與隊列的應用 摘 要：數(shù)據(jù)結(jié)構(gòu)是計算機中一個非常重要的分支，它是現(xiàn)實世界數(shù)據(jù)與計算機世界數(shù)據(jù)連接的關(guān)鍵，它主要涵蓋兩方面的內(nèi)容：邏輯層面的數(shù)據(jù)結(jié)構(gòu)和計算機存儲數(shù)據(jù)物理層的數(shù)據(jù)結(jié)構(gòu)。關(guān)于數(shù)據(jù)結(jié)構(gòu)中的線性表、棧、隊列，將上述兩方面的內(nèi)容進行介紹，進行橫向的比較，從而更清楚地看到它們之間的聯(lián)系與區(qū)別，并分析它們在現(xiàn)實計算中的應用。 關(guān)鍵詞：線性表；堆棧；隊列；應用開發(fā)Discussion on the Application of Stack and Queue Abstract: Data structure is a very important branch of a computer,

2、it is the key of the connection of real world data and computer world data,it mainly covers the following two contents:logic level data structure and computer data storage physical layer data structure.About the data structure of the linear list,stack,queue,it introduces the content of the above-men

3、tioned two aspects,carries on the horizontal comparison,thus more clearly see the relationship and difference between them.And analyzes them in real in the calculation of the application.Key words: Linear List; Stack;Queue;Application Development0 引言 棧和隊列可以看作線性表的特例,它們都具有和線性表相同的存儲方式,順序存儲和鏈式存儲,棧有順序棧和鏈

4、式棧,隊列有順序隊列和鏈式隊列。但從數(shù)據(jù)類型角度看,它們是和線性表大不相同的兩類重要的抽象數(shù)據(jù)類型。由于它們被廣泛應用在各種軟件系統(tǒng)中,因此在面向?qū)ο蟮某绦蛟O計中,它們是多型數(shù)據(jù)類型12。1 基本概念 1.1 線性表的概念和特性線性表是有限元素（a1,a2,a3，an）有序序列的集合，a1,a2，an都是完全相同結(jié)構(gòu)的數(shù)據(jù)類型，同時它們之間的排列嚴格有序，其中任何元素都對應唯一的前驅(qū)以及唯一的后繼。這樣一個序列可以有查詢、刪除、插入隊列任何位置的數(shù)據(jù)操作。1.2 棧的概念和特性棧作為一種限定性線性表，它限定插入和刪除操作都在表的同一端進行。允許插入和刪除元素的一端稱為棧頂，另一端為棧底；棧底固

5、定，棧頂浮動。棧的插入操作被形象地稱為進?；蛉霔＃瑒h除操作稱為出?；蛲藯?。我們只能從一端取出放入數(shù)據(jù)，即壓入棧和彈出棧，所以它的順序是“后進先出”，如圖1。作者簡介：劉碧霞(1993年)，女，本科，1063384634。 31.3 隊列的概念和特性隊列與棧類似，是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素。允許插入元素的一端稱為隊尾，允許刪除元素的一端稱為隊頭。它的操作不同的地方是兩端存、取數(shù)據(jù)，且僅僅是一端?。狀^）一端存（隊尾），所以它的順序是“先進 1先出”，如圖2。圖1 棧 圖2 隊列2 存儲結(jié)構(gòu)2.1 順序結(jié)構(gòu)線性表是用一定大小的數(shù)據(jù)來存放線性表，數(shù)組長度代

6、表線性表的長度，元素在數(shù)組的位置代表元素在線性表的位置。但對數(shù)組中元素不能跳躍插入，因為線性表中元素是順序且連接著的，不像數(shù)組中間可以空元素。同時刪除元素時，必須大量移動剩下的元素，因為必須實現(xiàn)其連續(xù)性。插入元素同樣需要大量移動數(shù)據(jù)。因此這樣存儲的運行效率并不夠高。所以對于有著頻繁插入和刪除運算的線性表，是不適合采用順序存儲的。堆棧是類似于線性表，利用數(shù)組存儲，只從這個數(shù)組的一端插入和刪除數(shù)據(jù)，不存在從中間“挖”數(shù)據(jù)，故不存在大量數(shù)據(jù)移動的問題，唯一不足的是數(shù)組大小是有限的，會存在棧滿的現(xiàn)象。如果數(shù)組大小定義過大，則又有大量存儲空間沒有被利用，會有資源浪費。隊列是初始存儲類似于線性表，但由于只

7、能從一邊進入另一邊出，所以數(shù)據(jù)會隨著數(shù)據(jù)操作而不斷“前進”，使隊列像一條“蠕蟲”一樣慢慢“爬過”隊列定義的全部空間，而且“爬過”的空間就無法再次得到運用。“蠕蟲”爬到數(shù)組盡頭之后則無法前進，而此時很可能數(shù)組前端還有大量的數(shù)據(jù)未得到使用。因此我們將一個數(shù)組看作是“相連”的，即將整個數(shù)組看做一個環(huán)形，而隊列“蠕蟲”則會在這個環(huán)形軌道中持續(xù)“爬動”，直到數(shù)據(jù)裝滿整個數(shù)據(jù)空間。但這里還有第二個問題，這樣的定義之后隊列空與滿，指向隊頭的front與指向隊尾的rear所處的相對位置是完全一樣的。這樣一個類似于“活塞”的工具，它總是緊鄰隊列中第一個數(shù)據(jù)元素，是可以移動的，但它本身不存放任何數(shù)據(jù)。同時將隊頭指

8、針指向這個“活塞”，那么隊空與隊滿的沖突情況就得以避免。2.2 鏈式結(jié)構(gòu)由于數(shù)組的靜態(tài)分配、不易擴充、插入刪除會有大量數(shù)據(jù)移動等種種局限性，我們引入鏈式存儲方式。通過動態(tài)分配存儲空間，最有效地利用空間。線性表是通過動態(tài)分配，分配物理上不一定相鄰的存儲單元。為表示他們的連續(xù)性連接性，再在分配這個存儲單元時，附加一部分存儲單元指針域（也叫鏈接域）來指出這個元素的后繼元素的存儲地址。這樣前面出現(xiàn)的刪除時間復雜度高算法效率低的問題就得到了解決。但凡事都有兩面性，插入刪除操作雖然高效，但它在查找上的效率卻不如數(shù)組方式，它無法訪問任意位置的元素，也無法根據(jù)現(xiàn)在所處的位置（current指針處）去訪問它前面

9、的數(shù)據(jù)。對于這些不足，我們也提出一些解決方案，通過循環(huán)鏈表（將尾部的鏈接指向線性表的頭部）或通過雙向鏈表（元素中增加指針，指針指向直接前驅(qū)元素）。這樣的鏈式存儲 24多節(jié)省了操作的時間，但需要更多的存儲空間。堆棧是類似于線性表的鏈式存儲，并且它的操作更為簡單。這種存儲相對于順序存儲，鏈式的堆?；旧蠜]有棧滿的情況。棧頭是最后進入的數(shù)據(jù)，棧尾是先進入的數(shù)據(jù)。隊列與前面類似。用鏈表表示隊列，僅限制在表頭刪除和表位插入。有兩個分別指向隊頭和隊尾的頭指針和尾指針?？盏逆滉犃械呐袥Q條件是，頭指針和尾指針均指向頭結(jié)點。 53 棧與隊列的部分應用開發(fā)3.1 棧的應用開發(fā)數(shù)制轉(zhuǎn)換十進制數(shù)N和其他d進制數(shù)的轉(zhuǎn)換

10、是計算機實現(xiàn)計算的基本問題，其解決方法很多，其中一個簡單算法基于下列原理：N =(N div d)×d + N mod d (其中，div為整除運算，mod為求余運算）假設現(xiàn)要編制一個滿足下列要求的程序：對于輸入的任意一個非負十進制整數(shù)，打印輸出與其等值的八進制數(shù)。由于上述計算過程是從低位到高位順序產(chǎn)生八進制數(shù)的各個數(shù)位，而打印輸出，一般來說應從高位到低位進行，恰好和計算過程相反。因此，若將計算過程中得到的八進制數(shù)的各位順序進棧，則按出棧序列打印輸出的即為與輸入對應的八進制數(shù)。棧操作的序列是直線式的，即先一味地入棧，然后一味地出棧。也許，有的讀者會提出疑問：用數(shù)組直接實現(xiàn)不也很簡單嗎

11、？仔細分析上述算法不難看出，棧的引入簡化了程序設計的問題，劃分了不同的關(guān)注層次，使思考范圍縮小了。而用數(shù)組不僅掩蓋了問題的本質(zhì)，還要分散精力去考慮數(shù)組下標增減等細節(jié)問題。3.2 隊列的應用開發(fā)3.2.1 打印楊輝三角在這一部分中，我們介紹利用隊列打印楊輝三角形的算法。楊輝三角形的特點是兩個腰上的數(shù)字都為1，其它位置上的數(shù)字是其上一行中與之相鄰的兩個整數(shù)之和。所以在打印過程中，第i 行上的元素要由第i-1行中的元素來生成。我們可以利用循環(huán)隊列實現(xiàn)打印楊輝三角形的過程。在循環(huán)隊列中依次存放第i-1 行上的元素，然后逐個出隊并打印，同時生成第i行元素并入隊。3.2.2 鍵盤輸入循環(huán)緩沖區(qū)問題在操作系

12、統(tǒng)中，循環(huán)隊列經(jīng)常用于實時應用程序。例如，當程序正在執(zhí)行其它任務時，用戶可以從鍵盤上不斷鍵入所要輸入的內(nèi)容。很多字處理軟件就是這樣工作的。系統(tǒng)在利用這種分時處理方法時，用戶鍵入的內(nèi)容不能在屏幕上立刻顯示出來，直到當前正在工作的那個進程結(jié)束為止。但在這個進程執(zhí)行時，系統(tǒng)是在不斷地檢查鍵盤狀態(tài)，如果檢測到用戶鍵入了一個新的字符，就立刻把它存到系統(tǒng)緩沖區(qū)中，然后繼續(xù)運行原來的進程。當前工作的進程結(jié)束后，系統(tǒng)就從緩沖區(qū)中取出鍵入的字符，并按要求進行處理。這里的鍵盤輸入緩沖區(qū)采用了循環(huán)隊列。隊列的特性保證了輸入字符先鍵入、先保存、先處理的要求，循環(huán)結(jié)構(gòu)又有效地限制了緩沖區(qū)的大小，并避免了假溢出問題。 64 結(jié)語研究和比較了數(shù)據(jù)結(jié)構(gòu)中棧和隊列,進一步加深了對數(shù)據(jù)結(jié)構(gòu)中棧和隊列的理解,總結(jié)得出其具有相同的邏輯結(jié)構(gòu),可以采用相同的存儲方法、具有不同的運算特點和都有廣泛的應用價值等,并在應用舉例編程中應用這些思想。參考文獻：1Weiss M A.Data Structure and Algorithm Analysis in CM.Addision-Wesley Longman,1998:23