簡(jiǎn)介

執(zhí)行棧是計(jì)算機(jī)科學(xué)中存儲(chǔ)有關(guān)正在運(yùn)行的子程序的消息的棧。經(jīng)常被用于存放子程序的返回地址。在調(diào)用任何子程序時(shí)，主程序都必須暫存子程序運(yùn)行完畢后應(yīng)該返回到的地址。因此，如果被調(diào)用的子程序還要調(diào)用其他的子程序，其自身的返回地址就必須存入執(zhí)行棧，在其自身運(yùn)行完畢后再行取回。在遞歸程序中，每一層次遞歸都必須在執(zhí)行棧上增加一條地址，因此如果程序出現(xiàn)無限遞歸（或僅僅是過多的遞歸層次），執(zhí)行棧就會(huì)產(chǎn)生棧溢出。

棧棧(stack)是限定僅在表尾進(jìn)行插入或刪除操作的線性表。因此，對(duì)棧來說，表尾端有其特殊含義，稱為棧頂(top)，相應(yīng)地，表頭端稱為棧底(bottom)1。

棧也可以是指計(jì)算機(jī)內(nèi)存中由程序指定的一個(gè)后進(jìn)先出(LIFO)存儲(chǔ)區(qū)或CPU內(nèi)部的一個(gè)LIFO寄存器組。前者稱軟棧，后者稱硬棧。軟棧的一端是固定的，另一端是浮動(dòng)的，浮動(dòng)的一端稱為棧頂。所有信息的存入和取出都只能在棧頂進(jìn)行，而且是在堆棧指示字寄存器的配合下，按LIFO原則工作的。硬棧棧頂一端是固定的，壓入的數(shù)據(jù)項(xiàng)占據(jù)棧頂，棧中原有的數(shù)據(jù)項(xiàng)都依次向棧底方向移動(dòng)；彈出數(shù)據(jù)時(shí)，最后進(jìn)棧的數(shù)據(jù)項(xiàng)先被彈出，下面各級(jí)數(shù)據(jù)項(xiàng)依次向棧頂方向移動(dòng)。軟棧和硬棧功能均相同，主要作為L(zhǎng)IFO緩沖存儲(chǔ)器，用于中斷處理、子程序嵌套及暫存數(shù)據(jù)。在程序中斷時(shí)，堆棧(自動(dòng))保存程序計(jì)數(shù)器、狀態(tài)寄存器及工作寄存器的內(nèi)容，并在中斷結(jié)束后把這些現(xiàn)場(chǎng)內(nèi)容恢復(fù)到相應(yīng)的寄存器中。

功能執(zhí)行棧的主要功能是存放返回地址。除此之外，調(diào)用棧還用于存放：

本地變量：子程序的變量可以存入調(diào)用棧，這樣可以達(dá)到不同子程序間變量分離開的作用。

參數(shù)傳遞：如果寄存器不足以容納子程序的參數(shù)，可以在調(diào)用棧上存入?yún)?shù)。

環(huán)境傳遞：有些語言（如Pascal與Ada）支持“多層子程序”，即子程序中可以利用主程序的本地變量。這些變量可以通過調(diào)用棧傳入子程序。

在較底層語言（如匯編語言與C語言中），程控消息與數(shù)據(jù)可能一同被存入調(diào)用棧中，因此造成安全隱患，可能允許惡意程序通過棧緩沖區(qū)溢出(stack buffer overflow)來獲取程序的控制權(quán)。

堆棧溢出堆棧溢出（英語：stack overflow）在計(jì)算機(jī)科學(xué)中是指使用過多的內(nèi)存時(shí)導(dǎo)致調(diào)用堆棧產(chǎn)生的溢出[1]。堆棧溢出的產(chǎn)生是由于過多的函數(shù)調(diào)用，導(dǎo)致調(diào)用堆棧無法容納這些調(diào)用的返回地址，一般在遞歸中產(chǎn)生。堆棧溢出很可能由無限遞歸（Infinite recursion）產(chǎn)生，但也可能僅僅是過多的堆棧層級(jí)。

堆棧溢出在內(nèi)核設(shè)計(jì)中尤其危險(xiǎn)，因此很多入門內(nèi)核設(shè)計(jì)教程建議用戶不要嘗試使用遞歸程序；而是基于安全和性能考量，改用循環(huán)處理問題。

遞歸概述是計(jì)算機(jī)問題求解的一種算法.是一種處理過程，這種過程的某一步要用到它自身的上一步(或上幾步)的結(jié)果。一個(gè)直接或間接地調(diào)用自己的過程稱為遞歸過程.在本過程中出現(xiàn)調(diào)用本過程自身的過程稱為直接遞歸過程；若過程P包含著對(duì)另一過程Q的引用，而Q又直接或間接地引用P，則稱P為間接遞歸過程。一個(gè)使用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。在數(shù)學(xué)定義和計(jì)算機(jī)算法中，遞歸技術(shù)是一種特別有力的工具。遞歸函數(shù)或遞歸過程的應(yīng)用往往使函數(shù)的定義和算法的描述比使用非遞歸方法更簡(jiǎn)明。

遞歸過程在程序設(shè)計(jì)中，使一個(gè)過程本身用 作一個(gè)子過程，這一做法往往是很方便的。如果過程這樣做，就稱為遞歸的。在處置符號(hào)表達(dá)式中，遞歸 過程尤為自然，因?yàn)檫@樣的程序結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)相匹配。至于程序設(shè)計(jì)語言，遞歸過程是十分自然的；在語言的定義中要求一個(gè)專門的語句來禁止它們。 但是，它們的實(shí)現(xiàn)就要求編譯一個(gè)特種的目標(biāo)代碼， 象Fortran這樣的早期程序設(shè)計(jì)語言中是不容許的。 問題在于：程序中的變量與機(jī)器中的存儲(chǔ)單元相對(duì)應(yīng)，當(dāng)程序被它本身調(diào)用時(shí)，它將使用這些相同的存儲(chǔ)單元，改寫它們?cè)鹊膬?nèi)容。所以，遞歸程序使用 一個(gè)稱為棧的數(shù)據(jù)結(jié)構(gòu)，用來把必須保存的寄存器內(nèi)容存儲(chǔ)起來。這一存儲(chǔ)可在進(jìn)入子例程之前由調(diào)用程序來完成，或者可在使用這些寄存器之前由子例程來完成，后者較常用。

在寄存器已保存在棧上之后，進(jìn)入棧的索引增大到存儲(chǔ)的寄存器數(shù)，因而棧上其后的保存將使用新的寄器。當(dāng)存在子例程時(shí)，保存的寄存器的內(nèi)容從?；謴?fù)到它們?cè)鹊闹?，棧指針按其原先增加的量減少。這項(xiàng)工作是根據(jù)如何存入的而通過相應(yīng)的 調(diào)用程序或子例程來完成的。另一種方法是使用棧作所有的暫時(shí)寄存器。在這種情況下，無需把數(shù)據(jù)傳來傳去，只需在子例程進(jìn)入與離開時(shí)改變棧指針。但是，這種方法對(duì)某些機(jī)器可能會(huì)用盡它的索引能力， 而這能力也是其他用途所需要的。遞歸程序可用任 何程序設(shè)計(jì)語言通過顯式地把保存和恢復(fù)進(jìn)行程序 設(shè)計(jì)的方法來編寫。在常規(guī)基礎(chǔ)上使用遞歸子例程的第一個(gè)語言是 Newell、Shaw和Simon的IPL語言。用表當(dāng)作棧使 用，保存與恢復(fù)顯然由程序員完成。第一個(gè)提供用于 遞歸的自動(dòng)機(jī)構(gòu)是Lisp。Algol和其后繼者Pascal和 Ada也容許遞歸，APL、PL/I、C和Snobol等其他語 言也一樣。許多計(jì)算機(jī)有處置棧的專用指令(例如，Digital Equipment DEC-10的PUSH和POP指令)。其他機(jī)器，例如Burroughs B5000和其后繼者，具有直接使用硬件棧的指令。這些專用的設(shè)施對(duì)于遞歸程序設(shè)計(jì)的效率有適度的增加2。