什么是棧?數(shù)據(jù)結(jié)構(gòu)中棧如何實(shí)現(xiàn)

　　今天放松一下，我們來(lái)看看數(shù)據(jù)結(jié)構(gòu)中的棧，這節(jié)的知識(shí)點(diǎn)可以說(shuō)是數(shù)據(jù)結(jié)構(gòu)中最容易上手的知識(shí)點(diǎn)了，其實(shí)比起鏈表，其實(shí)鏈表也有棧和隊(duì)列的模型，鏈表的頭插其實(shí)就是后進(jìn)先出，鏈表的尾插其實(shí)就是先進(jìn)先出，這不就是棧和隊(duì)列嗎，哈哈，不知道學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候有沒有意識(shí)到這一點(diǎn)，但是棧和隊(duì)列和鏈表還是有所區(qū)別的，我們來(lái)看看。

　　首先了解一下，什么是棧？ 棧（stack）又名堆棧，它是一種運(yùn)算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。這一端被稱為棧頂，相對(duì)地，把另一端稱為棧底。向一個(gè)棧插入新元素又稱作進(jìn)棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個(gè)棧刪除元素又稱作出?；蛲藯＃前褩ｍ斣貏h除掉，使其相鄰的元素成為新的棧頂元素。?？梢杂脕?lái)在函數(shù)調(diào)用的時(shí)候存儲(chǔ)斷點(diǎn)，做遞歸時(shí)要用到棧！最著名的實(shí)例便是漢諾塔，漢諾塔可以用遞歸來(lái)實(shí)現(xiàn)。棧的生長(zhǎng)方向是從高地址到低地址。每個(gè)函數(shù)的每次調(diào)用，都有它自己獨(dú)立的一個(gè)棧幀，這個(gè)棧幀中維持著所需要的各種信息。寄存器ebp指向當(dāng)前的棧幀的底部（高地址），寄存器esp指向當(dāng)前的棧幀的頂部（低地址）。注意：EBP指向當(dāng)前位于系統(tǒng)棧最上邊一個(gè)棧幀的底部，而不是系統(tǒng)棧的底部。嚴(yán)格說(shuō)來(lái)，“棧幀底部”和“棧底”是不同的概念;ESP所指的棧幀頂部和系統(tǒng)棧的頂部是同一個(gè)位置。在操作系統(tǒng)中，每一個(gè)線程都有一個(gè)棧，但是每個(gè)應(yīng)用程序通常都只有一個(gè)堆，當(dāng)然在為不同類型分配內(nèi)存的時(shí)候使用多個(gè)堆并不是不可能。

　　那棧有什么特點(diǎn)？

　　1. 和堆一樣存儲(chǔ)在計(jì)算機(jī) RAM 中。

　　2. 在棧上創(chuàng)建變量的時(shí)候會(huì)擴(kuò)展，并且會(huì)自動(dòng)回收。

　　3. 相比堆而言在棧上分配要快的多。

　　4. 用數(shù)據(jù)結(jié)構(gòu)中的棧實(shí)現(xiàn)。

　　5. 存儲(chǔ)局部數(shù)據(jù)，返回地址，用做參數(shù)傳遞。

　　6. 當(dāng)用棧過(guò)多時(shí)可導(dǎo)致棧溢出（無(wú)窮次（大量的）的遞歸調(diào)用，或者大量的內(nèi)存分配）。

　　7. 在棧上的數(shù)據(jù)可以直接訪問(wèn)（不是非要使用指針訪問(wèn)）。

　　8. 如果你在編譯之前精確的知道你需要分配數(shù)據(jù)的大小并且不是太大的時(shí)候，可以使用棧。

　　9. 當(dāng)你程序啟動(dòng)時(shí)決定棧的容量上限。