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

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

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

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