堆棧演算法

Ⅰ 堆棧相關演算法的實驗驗證 [實驗目的] 驗證順序存儲的堆棧及其上的基本操作。（c++）

目錄

序

堆棧是什麼？

實現方式

靜態數組堆棧

動態數組堆棧

鏈式堆棧

總結

序

我一直在想一個問題，我怎麼能把一件事情說的明白呢？尤其是程序方面的知識點。思路清楚是非常重要的（只有思路清楚，表達清楚了，才能一目瞭然），這個清楚的思路怎麼表現出來？我努力去做這件事情。這篇主要圍繞堆棧來展開話題。

Ⅱ 什麼事堆棧,堆棧有哪些運算,堆棧怎樣存儲

stack,其實就是一塊內存空間,關鍵在於他的用途.
1.對於程序指令來說
執行exe時,程序都會默認分配1M堆棧空間,vs2008等開發軟體都可以進行調整實際大小.
指令變成一條條機器碼,cpu會一條條執行.
例子:
xxxxxxx
call 0x403650 <- --
yyyyy
在執行call命令時,cpu會把下一條指令地址寫入堆棧地址空間中,當然也包括其他信息.
0x403650相當於一個子程序的地址,完事後,必然有一個ret之類的指令.這時,cpu根據先前保存的地址,也就是yyyyy這條指令所對應的地址.這樣就能繼續往下執行了.
關於這一點,用ollydbg好好玩一下,馬上就清楚了.

2.一般的應用程序編寫.
我們在編寫程序時,有時採用堆棧結構,有時採用隊列結構,這跟所採用的演算法有很大關系.
最常見的遞歸演算法,按遞歸展開的話,所有的細節就跟第1點完全一樣,好處是,大都程序員根本不關心象第1點所描述的細節.只知道其調用過程和最終執行結果.具體細節可能就不關心了.

當把遞歸演算法 用非遞歸演算法寫時,很可能你就要引入堆棧結構(其實就是人為手動申請一個內存空間,比如buffer[遞歸最深層數], 這樣,就可以編寫出直觀的順序結構的代碼. cpu也不用著因調用子程序,一次次把相關信息寫入系統的堆棧中(第1點所說)..因為buffer[]的存在就是為了避免這種情況.

--------------------
stack最常用兩種操作,push和pop. 你可以用c或是c++ 標准庫提供的實現.
如果不是大工程,基本上沒必要這么做.
搞個數組 buf[], 再搞個索引變數int index,用來指示top位置. 寫入數據時,index++,取出數據時index--

3.最常用的,但易忽略的.
平常所說的,局部變數就是在堆棧中分配的.所以他出了作用域就自動釋放了.
c語言很容易理解,不容易出錯.
但c++中,編譯器有不同的策略.
比如
CTeacher t= bar();
--
CTeacher bar()
{
CTeacher xx;
為CTeacher的成員賦值
return xx.
}
你一定為這里xx對象是局部變數,出了函數作用域,對應的內存主釋放了.
CTeacher t= bar();
因為bar()是返回一個Cteacher對象,所以這里就要執行拷貝構造函數,
你會奇怪,問題是bar()返回的對象是無效的.但執行卻不會出錯.
為什麼?
首先對堆棧的理解是對.只是c++編譯器內部會改寫bar()這個函數.
變成 void bar(CTeacher& tmp)
這樣,t就作為引用參數傳入了,函數內部創建臨時對象,然後賦值給引用對象就成了.結果當然正確了.

4. 是第2點的延伸,相當重要.
一些大的應用工程,往往配合堆來對內存進行管理.
以後你接觸一些第三方程序,一定會奇怪,要動態申請內存,直接new或malloc一個對象不就行了么,為什麼要這么麻煩.
其中一個重要原因:減少碎片,提高內存使用效率.
你先申請大的空間(new/malloc),然後藉助stack的特性來管理和控制這塊空間!!!
-------------------------------

ps:理解到這幾層差不多夠用了

Ⅲ 堆棧是什麼意思

問題一：什麼叫做堆棧？ 堆和棧是兩個不同的概念。 堆（heap）上分配的內存，系統不釋放，而且是動態分配的。棧（stack）上分配的內存系統會自動釋放，它是靜態分配的。運行時棧叫堆棧。棧的分配是從內存的高地址向低地址分配的，而堆則相反。由malloc或new分配的內存都是從heap上分配的內存，從heap上分配的內存必須有程序員自己釋放，用free來釋放，否則這塊內存會一直被佔用而得不到釋放，就出現了「內存泄露（Memory Leak）」。這樣會造成系統的可分配內存的越來越少，導致系統崩潰。 堆棧是一種執行「後進先出」演算法的數據結構。 設想有一個直徑不大、一端開口一端封閉的竹筒。有若干個寫有編號的小球，小球的直徑比竹筒的直徑略小。現在把不同編號的小球放到竹筒裡面，可以發現一種規律：先放進去的小球只能後拿出來，反之，後放進去的小球能夠先拿出來。所以「先進後出」就是這種結構的特點。 堆棧就是這樣一種數據結構。它是在內存中開辟一個存儲區域，數據一個一個順序地存入（也就是「壓入――push」）這個區域之中。有一個地址指針總指向最後一個壓入堆棧的數據所在的數據單元，存放這個地址指針的寄存器就叫做堆棧指示器。開始放入數據的單元叫做「棧底」。數據一個一個地存入，這個過程叫做「壓棧」。在壓棧的過程中，每有一個數據壓入堆棧，就放在和前一個單元相連的後面一個單元中，堆棧指示器中的地址自動加1。讀取這些數據時，按照堆棧指示器中的地址讀取數據，堆棧指示器中的地址數自動減 1。這個過程叫做「彈出pop」。如此就實現了後進先出的原則。 而堆棧寄存器就是存放堆棧的寄存器。

問題二：什麼叫堆棧 堆棧是內存區開辟出來為函數中定義的變數（除了new以外的定義）提供存儲空間的區域。
顧名思義，數據在堆棧中 的存儲就是一個一個堆上去的，就是說後放的變數存在最上面（棧頂），所以從堆棧中取出變數時它最先被取出，（後進先出）。

問題三：堆棧的意思和作用 堆棧就是一個特殊內存區域，
用來存放數據
可以用指令PUSH ,POP 操作
主要是用來存放臨時數據，比如局部變數，某個函數過程中定義的變數
堆棧是先進後出方式
比如說有個過程求和
int fun(int a,int b)
{
return a+b;
}
void main()
{
int z;
z=fun(5,6)
printf(%d,z)
}
調用fun過程時操作系統會使用堆棧來傳遞參數，
首先PUSH 5
PUSH 6
CALL FUN
又或者在調用過程前將各個寄存器先保存起來因為數量有限在本過程中可能用到同樣的寄存器被覆蓋原來的值
main
mov ax,6
mov bx,7
call proc
...
proc1 proc
push ax ;先入
push bx
子過程程序中用到AX,BX
pop bx
pop ax ;後出
ret
proc1 endp

問題四：什麼是堆棧及堆棧的作用是什麼 堆棧是小說中常用的人物塑造方法，通常是為一個小人物所用。舉個例子，某劍客非常之吊，被稱為天下無敵。可是，一個小人物在與他正面的斗爭中，不用任何手段就擊敗了他，表現出他驚人的實力。這就是對這個小人物的堆棧，為的就是把他通過別人巨大實力的轉換成這個人物的威望。這就是堆棧

問題五：堆棧向下增長是什麼意思？ 堆和棧是兩個概念，堆向上增長，棧向下增長。
向下增長的意思是：從棧申請的內存地址會越來越小，
而從堆申請的內存地址會越來越大。

問題六：誰給詳細解釋一下plc的堆棧是什麼意思，是在理解不了 PLC中CPU進行運算過程中，在需要進堆棧的時候才進堆棧。
比如：
1、不需要進堆棧的
LD X0
AND X1
OUT Y0.
這樣的不需要進堆棧，因為每次運算的結果都存在CPU累加器A裡面。（書上講的）
2、需要進堆棧的，這段指令在執行過程中，就有數據進堆棧。（分號後加註釋）
LD X0 ；取了X0的狀態放進累加器
OR X1；把X1的狀態與累加器內狀態進行 或 運算。
LD X2；這時候如果直接取X2的狀態進累加器，那前面兩條指令的就白幹了。
所有這條指令有隱 含操作，那就是把前面兩條指令運算的結果，進行進堆棧保護，
然後再把X2的狀態取進累加器。
OR X3；接著，取X3的狀態與累加器或 運算
ANB ；這條執行是，就是將堆棧最上面的狀態值（也就是前面進堆棧被保護的）
與當前累加器的狀態進行與運算。這也就是書上說的，塊 與指令。
OUT Y0；輸出。
從上面分析我總結了，只要是出現LD，必須要有輸出。沒輸出，再有LD，那必定有進堆棧操作。
這個進堆棧是PLC系統自己完成。只要你編程正確，也沒必要理會他。

問題七：堆棧和棧有什麼區別？ 堆和棧是兩個不同的概念，堆是動態內存，malloc，new等操閥在堆裡面分配空間；棧裡面放函數調用參數，局部變數。
對專業人士而言，一般習慣把堆和棧分開來講。有些地方也把棧籠統地叫做堆棧，也就是說你這里說的堆棧就是指棧。你只要搞清楚堆和棧的區別就可以了。

問題八：堆棧是什麼意思？如果堆棧的入棧系列是a,b,c,d,e，則輸出序列是什麼?並解釋一下! 堆棧是一種「後進先出」的數據結構。出棧序列「e,d,c,b,a。後進入的先出來。

問題九：棧是什麼意思？ 棧（stack）在計算機科學中是限定僅在表尾進行插入或刪除操作的線性表。 棧是一種數據結構，是只能在某一端插入和刪除的特殊線性表。它按照後進先出的原則存儲數據，先進入的數據被壓入棧底，最後的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最後一個數據被第一個讀出來）。 棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數為零時稱為空棧。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。 棧也稱為後進先出表（LIFO--Last IN First Out表龔。 棧可以用來在函數調用的時候存儲斷點，做遞歸時要用到棧！
上面已經說得很清楚了
雖然是復制的