3.3 棧與隊(duì)列的比較

棧與隊(duì)列既是兩種重要的線性結(jié)構(gòu)，也是兩種操作受限的特殊線性表。為了讓讀者能夠更好地掌握它們的使用特點(diǎn)，在此對棧和隊(duì)列做一個(gè)比較。

1．棧與隊(duì)列的相同點(diǎn)

（1）都是線性結(jié)構(gòu)，即數(shù)據(jù)元素之間具有“一對一”的邏輯關(guān)系。

（2）插入操作都限制在表尾進(jìn)行。

（3）都可在順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)上實(shí)現(xiàn)。

（4）在時(shí)間代價(jià)上，插入與刪除操作都需常數(shù)時(shí)間；在空間代價(jià)上，情況也相同。

（5）多鏈棧和多鏈隊(duì)列的管理模式可以相同。在計(jì)算機(jī)系統(tǒng)軟件中，經(jīng)常會出現(xiàn)同時(shí)管理和使用兩個(gè)以上棧或隊(duì)列的情況，在這種情景下，若采用順序存儲結(jié)構(gòu)實(shí)現(xiàn)棧和隊(duì)列，將會給處理帶來極大的不便，因而一般采用多個(gè)單鏈表來實(shí)現(xiàn)多個(gè)棧或隊(duì)列。圖3-27、圖3-28是多鏈棧和多鏈隊(duì)列的存儲結(jié)構(gòu)示意圖。它們將多個(gè)鏈棧的棧頂指針或鏈隊(duì)列的隊(duì)首、隊(duì)尾指針分別存放在一個(gè)一維數(shù)組中，從而很方便地實(shí)現(xiàn)了統(tǒng)一管理和使用多個(gè)棧或隊(duì)列。

2．棧與隊(duì)列的不同點(diǎn)

（1）刪除數(shù)據(jù)元素操作的位置不同。棧的刪除操作控制在表尾進(jìn)行，而隊(duì)列的刪除操作控制在表頭進(jìn)行。

（2）兩者的應(yīng)用場合不同。具有后進(jìn)先出（或先進(jìn)后出）特性的應(yīng)用需求，可使用棧式結(jié)構(gòu)進(jìn)行管理。例如：遞歸調(diào)用中現(xiàn)場信息、計(jì)算的中間結(jié)果和參數(shù)值的保存，圖與樹的深度優(yōu)先搜索遍歷都采用棧式存儲結(jié)構(gòu)加以實(shí)現(xiàn)。而具有先進(jìn)先出（后進(jìn)后出）特性的應(yīng)用需求，則要使用隊(duì)列結(jié)構(gòu)進(jìn)行管理。例如：消息緩沖器的管理，操作系統(tǒng)中對內(nèi)存、打印機(jī)等各種資源進(jìn)行管理，都使用了隊(duì)列。同時(shí)，可以根據(jù)不同優(yōu)先級的服務(wù)請求，按優(yōu)先級把服務(wù)請求組成多個(gè)不同的隊(duì)列。隊(duì)列也是圖和樹在廣度搜索遍歷過程中采用的數(shù)據(jù)結(jié)構(gòu)。

（3）順序棧可實(shí)現(xiàn)多棧空間共享，而順序隊(duì)列則不同。實(shí)際應(yīng)用中經(jīng)常會出現(xiàn)在一個(gè)程序中需要同時(shí)使用兩個(gè)棧或隊(duì)列的情況。若采用順序存儲，就可以使用一個(gè)足夠大的數(shù)組空間來存儲多個(gè)棧，即讓多個(gè)棧共享同一存儲空間。圖3-29是兩個(gè)棧共享空間的示意圖。其中：把數(shù)組的兩端設(shè)置為兩棧各自的棧底，兩棧的棧頂從兩端開始向中間延伸。可以充分利用順序棧單向延伸的特性，使兩個(gè)棧的空間形成互補(bǔ)，從而提高存儲空間的利用率。然而，順序隊(duì)列就不能像順序棧那樣在同一個(gè)數(shù)組中存儲兩個(gè)隊(duì)列，除非總有數(shù)據(jù)元素從一個(gè)隊(duì)列轉(zhuǎn)入另一個(gè)隊(duì)列。