棧[計算機術語]

棧（stack）又名堆疊，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

基本信息

• 中文名：棧
• 英文名：stack

• 種類：數據結構
• 說法：進棧、出棧
• 堆疊幀：函式的返回地址和參數
• 定義：表頭進行插入和刪除操作的線性表
• 別名：堆疊

基本概念

定義：棧是限定僅在表頭進行插入和刪除操作的線性表。要搞清楚這個概念，首先要明白”棧“原來的意思，如此才能把握本質。"棧“者,存儲貨物或供旅客住宿的地方,可引申為倉庫、中轉站，所以引入到計算機領域裡，就是指數據暫時存儲的地方，所以才有進棧、出棧的說法。

首先系統或者數據結構棧中數據內容的讀取與插入（壓入push和 彈出pop）是兩回事！插入是增加數據，彈出是刪除數據 ，這些操作只能從棧頂即最低地址作為約束的接口界面入手操作 ，但讀取棧中的數據是隨便的沒有接口約束之說。很多人都誤解這個理念從而對棧產生困惑。 而系統棧在計算機體系結構中又起到一個跨部件互動的媒介區域的作用 即 cpu 與記憶體的交流通道 ，cpu只從系統給我們自己編寫的應用程式所規定的棧入口線性地讀取執行指令， 用一個形象的詞來形容它就是pipeline（管道線、流水線）。cpu內部互動具體參見 EU與BIU的概念介紹。

棧作為一種數據結構，是一種只能在一端進行插入和刪除操作的特殊線性表。它按照先進後出的原則存儲數據，先進入的數據被壓入棧底，最後的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最後一個數據被第一個讀出來）。棧具有記憶作用，對棧的插入與刪除操作中，不需要改變棧底指針。

棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數為零時稱為空棧。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。棧也稱為後進先出表。

棧可以用來在函式調用的時候存儲斷點，做遞歸時要用到棧！

以上定義是在經典計算機科學中的解釋。

在計算機系統中，棧則是一個具有以上屬性的動態記憶體區域。程式可以將數據壓入棧中，也可以將數據從棧頂彈出。在i386機器中，棧頂由稱為esp的暫存器進行定位。壓棧的操作使得棧頂的地址減小，彈出的操作使得棧頂的地址增大。

棧在程式的運行中有著舉足輕重的作用。最重要的是棧保存了一個函式調用時所需要的維護信息，這常常稱之為堆疊幀或者活動記錄。堆疊幀一般包含如下幾方面的信息：

1．函式的返回地址和參數

2． 臨時變數：包括函式的非靜態局部變數以及編譯器自動生成的其他臨時變數。

棧的模型

基本算法

1．進棧（PUSH）算法

①若TOP≥n時，則給出溢出信息，作出錯處理（進棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）；

②置TOP=TOP+1（棧指針加1，指向進棧地址）；

③S(TOP)=X，結束（X為新進棧的元素）；

2．退棧（POP）算法

①若TOP≤0，則給出下溢信息，作出錯處理(退棧前先檢查是否已為空棧， 空則下溢；不空則作②)；

②X=S(TOP)，（退棧後的元素賦給X）：

③TOP=TOP-1，結束（棧指針減1，指向棧頂）。

實現

棧分順序棧和鏈式棧，下面程式介紹了順序棧的實現。

pascal

1．數組型

Const

m=棧表目數的上限；

Type

stack=array[1..m] of stype; {棧類型}

Var

s:stack;{棧}

top:integer;

2．記錄型

const

m=棧表目數的上限；

type

stack=record

elem: array[1..m] of elemtp;

top:0..m; {棧頂指針}

end;

Var

s:stack;{棧}

C++代碼

C代碼

定義stack的簡單代碼：

stack<int> sta;

入棧：sta.push(x);

出棧：sta.pop();

判斷棧的大小： sta.size();

判斷棧是否為空：sta.empty();