從線性表談到棧與隊列

摘 要：數(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)實計算中的應(yīng)用。

關(guān)鍵詞：線性表；堆棧；隊列

中圖分類號：TP311.12 文獻標識碼：A 文章編號：1006-8937（2012）17-0081-02

1 邏輯關(guān)系

①線性表。線性表是有限元素（a1，a2，a3…，an）有序序列的集合，a1，a2…，an都是完全相同結(jié)構(gòu)的數(shù)據(jù)類型，同時它們之間的排列嚴格有序，其中任何元素都對應(yīng)唯一的前驅(qū)以及唯一的后繼。這樣一個序列可以有查詢、刪除、插入隊列任何位置的數(shù)據(jù)操作。

②堆棧。堆棧也是一個有序序列的集合，結(jié)構(gòu)上與線性表規(guī)定一樣。但它的運算受到嚴格的限制（故也叫限定性線性表）。這個序列中我們只能從一端取出放入數(shù)據(jù)，即壓入棧和彈出棧，所以它的順序是“先進先出”，如圖1所示。

③隊列。隊列與棧類似，屬于限定性線性表，它的操作不同的地方是兩端存、取數(shù)據(jù)，且僅僅是一端取（隊頭）一端（隊尾），所以它的數(shù)據(jù)是“先入先出”。

2 物理結(jié)構(gòu)

2.1 順序結(jié)構(gòu)

{1}線性表。用一定大小的數(shù)據(jù)來存放線性表，數(shù)組長度代表線性表的長度，元素在數(shù)組的位置代表元素在線性表的位置。但對數(shù)組中元素不能跳躍插入，因為線性表中元素是順序且連接著的，不像數(shù)組中間可以空元素。同時刪除元素時，必須大量移動剩下的元素，因為必須實現(xiàn)其連續(xù)性。插入元素同樣需要大量移動數(shù)據(jù)。因此這樣存儲的運行效率并不夠高。所以對于有著頻繁插入和刪除運算的線性表，是不適合采用順序存儲的。

{2}堆棧。類似于線性表，利用數(shù)組存儲，只從這個數(shù)組的一端插入和刪除數(shù)據(jù)，不存在從中間“挖”數(shù)據(jù)，故不存在大量數(shù)據(jù)移動的問題，唯一不足的是數(shù)組大小是有限的，會存在棧滿的現(xiàn)象。如果數(shù)組大小定義過大，則又有大量存儲空間沒有被利用，會有資源浪費。

{3}隊列。初始存儲類似于線性表，但由于只能從一邊進入另一邊出，所以數(shù)據(jù)會隨著數(shù)據(jù)操作而不斷“前進”，使隊列像一條“蠕蟲”一樣慢慢“爬過”隊列定義的全部空間，而且“爬過”的空間就無法再次得到運用。“蠕蟲”爬到數(shù)組盡頭之后則無法前進，而此時很可能數(shù)組前端還有大量的數(shù)據(jù)未得到使用。因此我們將一個數(shù)組看作是“相連”的，即將整個數(shù)組看做一個環(huán)形，而隊列“蠕蟲”則會在這個環(huán)形軌道中持續(xù)“爬動”，直到數(shù)據(jù)裝滿整個數(shù)據(jù)空間。但這里還有第二個問題，這樣的定義之后隊列空與滿，指向隊頭的front與指向隊尾的rear所處的相對位置是完全一樣的，如圖2、圖3所示。

這樣一個類似于“活塞”的工具，它總是緊鄰隊列中第一個數(shù)據(jù)元素，是可以移動的，但它本身不存放任何數(shù)據(jù)。同時將隊頭指針指向這個“活塞”，那么隊空與隊滿的沖突情況就得以避免，如圖4、圖5所示。

2.2 鏈 式

由于數(shù)組的靜態(tài)分配、不易擴充、插入刪除會有大量數(shù)據(jù)移動等種種局限性，我們引入鏈式存儲方式。通過動態(tài)分配存儲空間，最有效地利用空間。

線性表：通過動態(tài)分配，分配物理上不一定相鄰的存儲單元。為表示他們的連續(xù)性連接性，再在分配這個存儲單元時，附加一部分存儲單元——指針域（也叫鏈接域）來指出這個元素的后繼元素的存儲地址。這樣前面出現(xiàn)的刪除時間復(fù)雜度高算法效率低的問題就得到了解決。但凡事都有兩面性，插入刪除操作雖然高效，但它在查找上的效率卻不如數(shù)組方式，它無法訪問任意位置的元素，也無法根據(jù)現(xiàn)在所處的位置（current指針處）去訪問它前面的數(shù)據(jù)。對于這些不足，我們也提出一些解決方案，通過循環(huán)鏈表（將尾部的鏈接指向線性表的頭部）或通過雙向鏈表（元素中增加指針，指針指向直接前驅(qū)元素）。這樣的鏈式存儲多節(jié)省了操作的時間，但需要更多的存儲空間。

堆棧：類似于線性表的鏈式存儲，并且它的操作更為簡單。這種存儲相對于順序存儲，鏈式的堆棧基本上沒有棧滿的情況，存儲如圖6所示。

棧頭是最后進入的數(shù)據(jù)，棧尾是先進入的數(shù)據(jù)。

隊列：與前面類似，具體存儲如圖7所示。

3 應(yīng)用舉例

①線性表。一個數(shù)據(jù)表使用過后，可能下次還會再次被使用。比如輸入某漢字，首屏一般是常用漢字，那么就需要通過翻屏找到用戶需要的漢字，一般使用過一次后，接下來很大幾率再次使用它。漢字可以以鏈表中結(jié)點存儲，而第一屏僅顯示鏈表前面若干漢字，故要將之前使用過的漢字移動到第一結(jié)點的位置，提高漢字錄入效率。這是根據(jù)結(jié)點的使用（潛在）概率來決定存放的位置，如果不能取得每個結(jié)點的潛在使用概率，可以采用前移一個位置的方法，使用越多，前移越多。

②堆棧。首先是背包問題，假設(shè)有一個能容納總體積為T的背包，另有n個體積分別是w1，w2…wn個物品，現(xiàn)要在這幾件物品中選出若干件物品恰好裝滿背包，求滿足條件的所有解。然后采用嘗試回逆法，從0號物品開始順序選取物品，如果可以裝入背包（裝入后不滿），則將該物品的編號進棧。如果當前選定的物品k裝不進去（裝入后體積大于T）選擇下一個物品（k+1）嘗試裝入。如果尚未求得解，又已無物品可選，則說明上一個裝入的物品不合適，將堆棧退出一個背包編號，再從這個退出的編號的下一個編號物品嘗試。每求出一組解，輸出結(jié)果，再退出棧頂數(shù)據(jù)，再從當前退出的編號的下一個標號物品嘗試，直到堆棧為空（無退棧數(shù)據(jù)）且達到最大編號

③隊列。以列車重排進行分析，一列貨運列車共有 n 節(jié)車廂，每節(jié)車廂將停放在不同的車站。假定n個車站的編號分別為1～n，即貨運列車按照第n站至第1站的次序經(jīng)過這些車站。為了便于從列車上卸掉相應(yīng)的車廂，車廂的編號應(yīng)與車站的編號相同，這樣，在每個車站只需卸掉最后一節(jié)車廂。所以，給定任意次序的車廂，必須重新排列他們。假定重排n個車廂，可使用k個緩沖軌，將每個緩沖軌看成是一個隊列，用nowOut表示下一個輸出至出軌的車廂編號。火車車廂重排的算法用偽代碼描述如下：分別對k個隊列初始化；初始化下一個有愛輸出的車廂編號nowOut=1；依次取入軌中的每一個車廂編號。如果入軌中的車廂編號等于nowOut，則輸出該車廂：nowOut++。否則，考慮每一個緩沖軌隊列：for（j=1;j<=k;j++），取隊列j的對頭元素c。如果c=nowOut，則將隊列j的對頭元素出隊并輸出：nowOut++。如果入軌和緩沖軌的對頭元素沒有編號為nowOut的車廂，則求小雨入軌中第一個車廂編號的最大隊尾元素所在隊列編號j。如果j存在，則把入軌中的第一個車廂移至緩沖軌j；如果j不存在，但有多余一個空緩沖軌，則把入軌第一個車廂移至一個空緩沖軌；否則車廂無法重排，算法結(jié)束。

參考文獻：

[1] 曹玉鋒.數(shù)據(jù)結(jié)構(gòu)中線性表、棧與隊列[J].網(wǎng)絡(luò)科技時代(數(shù)字沖浪)，2002，(1).