基本介紹
- 中文名：堆疊溢出原理
- 堆疊：經常使用的抽象數據類型
- 特性：通常稱為後進先出(LIFO)佇列
- 堆疊：是一塊保存數據的連續記憶體
定義,為什麼使用堆疊?,堆疊區域,堆疊溢出,
定義
堆疊是一個在計算機科學中經常使用的抽象數據類型。堆疊中的物體具有一個特性: 最後一個放入堆疊中的物體總是被最先拿出來， 這個特性通常稱為後進先出(LIFO)佇列. 堆疊中定義了一些操作. 兩個最重要的是PUSH和POP。 PUSH操作在堆疊的頂部壓入一 個元素。POP操作相反， 在堆疊頂部推出一個元素， 並將堆疊的大小減一。
為什麼使用堆疊?
現代計算機被設計成能夠理解人們頭腦中的高級語言。 在使用高級語言構造程式時 最重要的技術是過程(procedure)和函式(function)。 從這一點來看， 一個過程調用可 以像跳轉(jump)命令那樣改變程式的控制流程， 但是與跳轉不同的是， 當工作完成時， 函式把控制權返回給調用之後的語句或指令。 這種高級抽象實現起來要靠堆疊的幫助。 堆疊也用於給函式中使用的局部變數動態分配空間， 同樣函式傳遞參數和函式返 回值也要用到堆疊。
堆疊區域
堆疊是一塊保存數據的連續記憶體。 一個名為堆疊指針(SP)的暫存器指向堆疊的頂部。 堆疊的底部在一個固定的地址。 堆疊的大小在運行時由核心動態地調整。 CPU實現指令 PUSH和POP， 向堆疊中添加元素和從中移去元素。 堆疊由邏輯堆疊幀組成。 當調用函式時邏輯堆疊幀被壓入棧中， 當函式返回時邏輯 堆疊幀被從棧中彈出。 堆疊幀包括函式的參數， 函式的局部變數， 以及恢復前一個堆疊 幀所需要的數據， 其中包括在函式調用時指令指針(IP)的值。 堆疊既可以向下增長(向記憶體低地址)也可以向上增長， 這依賴於具體的實現。 在我 們的例子中， 堆疊是向下增長的。 這是很多計算機的實現方式， 包括Intel， Motorola， SPARC和MIPS處理器。 堆疊指針(SP)也是依賴於具體實現的。 它可以指向堆疊的最後地址， 或者指向堆疊之後的下一個空閒可用地址。 在我們的討論當中， SP指向堆疊的最後地址。 除了堆疊指針(SP指向堆疊頂部的的低地址)之外， 為了使用方便還有指向幀內固定 地址的指針叫做幀指針(FP)。 有些文章把它叫做局部基指針(LB-local base pointer)。 從理論上來說， 局部變數可以用SP加偏移量來引用。 然而， 當有字被壓棧和出棧後， 這 些偏移量就變了。 儘管在某些情況下編譯器能夠跟蹤棧中的字操作， 由此可以修正偏移 量， 但是在某些情況下不能。 而且在所有情況下， 要引入可觀的管理開銷。 而且在有些 機器上， 比如Intel處理器， 由SP加偏移量訪問一個變數需要多條指令才能實現。 因此， 許多編譯器使用第二個暫存器， FP， 對於局部變數和函式參數都可以引用， 因為它們到FP的距離不會受到PUSH和POP操作的影響。 在Intel CPU中， BP(EBP)用於這 個目的。 在Motorola CPU中， 除了A7(堆疊指針SP)之外的任何地址暫存器都可以做FP。 考慮到我們堆疊的增長方向， 從FP的位置開始計算， 函式參數的偏移量是正值， 而局部 變數的偏移量是負值。 當一個例程被調用時所必須做的第一件事是保存前一個FP(這樣當例程退出時就可以 恢復)。 然後它把SP複製到FP， 創建新的FP， 把SP向前移動為局部變數保留空間。 這稱為 例程的序幕(prolog)工作。 當例程退出時， 堆疊必須被清除乾淨， 這稱為例程的收尾 (epilog)工作。 Intel的ENTER和LEAVE指令， Motorola的LINK和UNLINK指令， 都可以用於 有效地序幕和收尾工作。
