數(shù)據(jù)結(jié)構(gòu)教學(xué)棧和隊列

1、棧和隊列基本概念棧（stack）是限制插入和刪除只能在一個位置上進(jìn)行的表，該位置是表的末端，叫做棧的頂（top），它是后進(jìn)先出（LIFO）的。對棧的基本操作只有push（進(jìn)棧）和pop（出棧）兩種，前者相當(dāng)于插入，后者相當(dāng)于刪除最后的元素。由于棧在本質(zhì)上是一種受限制的表，所以可以使用任何一種表的形式來實現(xiàn)它，我們最常使用的一般有兩種：鏈表 數(shù)組 它們在復(fù)雜度上的優(yōu)缺點對比如下：新增和刪除元素時的時間復(fù)雜度 鏈表：在動態(tài)申請內(nèi)存（new或者malloc）上的花銷非常昂貴。 數(shù)組：幾乎沒有花銷，以常數(shù)O(1)時間運行，在帶有自增和自減尋址功能的寄存器上操作時，編譯器會把整數(shù)的push和pop操作編

2、譯成一條機(jī)器指令。 空間復(fù)雜度 鏈表：由于空間是動態(tài)申請、釋放的，因此不會浪費空間，而且只要物理存儲器允許，理論上能夠滿足最大范圍未知的情況。 數(shù)組：必須在初始化時指定棧的大小，有可能會浪費空間，也有可能不夠空間用。 結(jié)論如果對運行時的效率要求非常高，并且能夠在初始化時預(yù)知棧的大小，那么應(yīng)該首選數(shù)組形式；否則就應(yīng)該選用鏈表形式。 由于對棧的操作永遠(yuǎn)都是針對棧頂（top）進(jìn)行的，因此數(shù)組的隨機(jī)存取的優(yōu)點就沒有了，而且數(shù)組必須預(yù)先分配空間，空間大小也受到限制，所以一般情況下（對運行時效率的要求不是太高）鏈表應(yīng)該是首選。在C+的繼承機(jī)制下，棧的實現(xiàn)簡單得可怕。 :)一個影響棧的運行效率的問題是錯誤檢

3、測。我的棧實現(xiàn)中是仔細(xì)地檢查了錯誤的對空棧進(jìn)行top和pop操作，以及當(dāng)存儲空間不夠時進(jìn)行push操作是會引起異常的，顯然，我們不愿意出現(xiàn)這種情況，但是，如果把對這些條件的檢測放到代碼中，那就很可能要花費像實際棧操作那樣多的時間。由于這個原因，除非在錯誤處理極其重要的場合（例如在操作系統(tǒng)中），一般在棧中省去錯誤檢測就成了普通的慣用手法。一個良好的程序首先應(yīng)該是健壯的，這比效率還要重要，特別是對于棧這種最基本的數(shù)據(jù)結(jié)構(gòu)，它很可能會被作為基本的元素而被別的地方大量地使用。引入錯誤檢查機(jī)制的代價是：操作變得有些繁瑣.像棧一樣，隊列（queue）也是表。然而，使用隊列時插入在一端進(jìn)行而刪除則在另一端進(jìn)行，也就是先進(jìn)先出（FIFO）。隊列的基本操作是EnQueue（入隊），它是在表的末端（叫做隊尾（rear）插入一個元素；還有DeQueue（出隊），它是刪除（或返回）在表的開頭（叫做隊頭（front）的元素。隊列一般有鏈?zhǔn)疥犃泻脱h(huán)隊列兩種。鏈?zhǔn)疥犃邢喈?dāng)于我們在銀行中排隊，后來的人排到隊伍的最后，前面的人辦理完業(yè)務(wù)后就會離開，讓下一個人進(jìn)去；循環(huán)隊列則跟循環(huán)鏈表很相似。隊列的應(yīng)用一般來說是模擬現(xiàn)實生活中的一些離散現(xiàn)象，例如銀行排隊、打印機(jī)任務(wù)、接線員工作等等。還有的就是使用隊列來提高運行效率的算法，這些一般是在圖算法