摘 要：數據結構是計算機中一個非常重要的分支，它是現實世界數據與計算機世界數據連接的關鍵，它主要涵蓋兩方面的內容：邏輯層面的數據結構及計算機存儲數據物理層的數據結構。關于數據結構中的線性表、棧、隊列，文章將上述兩方面的內容進行介紹，進行橫向的比較，從而更清楚地看到它們之間的聯系與區(qū)別。并分析它們在現實計算中的應用。

關鍵詞：線性表；堆棧；隊列

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

1 邏輯關系

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

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

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

2 物理結構

2.1 順序結構

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

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

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

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

2.2 鏈 式

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

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

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

棧頭是最后進入的數據，棧尾是先進入的數據。

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

3 應用舉例

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

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

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

參考文獻：

[1] 曹玉鋒.數據結構中線性表、棧與隊列[J].網絡科技時代(數字沖浪)，2002，(1).