堆疊是一個抽象數據類型(ADT)，在大多數編程語言中常用。它被命名堆，因為它就像一個現實世界的堆，例如 - 撲克牌板或堆等。
一個真實世界的堆疊允許保存操作僅在一端進行。例如，我們只可以把或從堆疊頂部取出存儲卡或板。同樣地，堆疊ADT允許僅在一端執行所有數據操作。在任何特定時間，我們只能訪問一個堆疊的頂部元素。
這一特點使它成為後進先出的數據結構。 LIFO表示後進先出。這裏放置（插入或添加）最後元素，在第一次訪問。在堆的術語中，插入操作被稱為PUSH操作，刪除操作稱為POP操作。
堆疊表示
如下圖試圖描繪出堆疊及其操作 -
堆疊可通過數組，結構和鏈表來實現。堆疊可以是固定大小或它可動態調整。在這裏，我們要實現使用堆疊數組，這使用的是一個固定大小的堆疊實現。
基本操作
堆疊操作可能涉及初始化堆疊，使用它，然後去對其進行初始化。除了這些基本的東西，堆疊用於以下兩個主要的操作 -
-
push() − 推（存儲）在棧上的元素。
-
pop() − 除去（訪問）堆疊上的元素。
當數據被壓入堆疊。
要使用堆疊有效，我們需要檢查棧的情況也是如此。為了同樣的目的，下麵的功能添加到棧 -
-
peek() − 得到的堆疊頂部的數據元素，但不刪除它。
-
isFull() − 檢查堆疊是否滿了。
-
isEmpty() − 檢查堆疊是否為空的。
在任何時候，我們保持一個指向最後壓入堆疊的數據。這種指針總是代表堆疊的頂部，因此命名為：top（頂部）。頂部指針提供堆疊頂部的值，但不刪除它。
首先，我們應該瞭解程式，以支持堆疊功能 -
peek()
peek()函數演算法
begin procedure peek return stack[top] end procedure
peek()函數的 C語言編程實現，如下：
int peek() {
return stack[top];
}
isfull()
isfull()函數演算法：
begin procedure isfull
if top equals to MAXSIZE
return true
else
return false
endif
end procedure
isfull()函數的C語言編程實現
bool isfull() {
if(top == MAXSIZE)
return true;
else
return false;
}
isempty()
isEmpty()函數演算法
begin procedure isempty
if top less than 1
return true
else
return false
endif
end procedure
isEmpty()函數的 C語言編程實現略有不同。我們初始化頂部值為 -1, 由於指數數組從0開始。因此，我們檢查如果頂部是小於零或-1，以確定是否堆疊是空的。下麵的代碼
bool isempty() {
if(top == -1)
return true;
else
return false;
}
PUSH/推送操作
把一個新的數據元素到堆疊的過程被稱為推入操作。推操作涉及一系列步驟 -
-
步驟 1 − 檢查堆疊是否滿了
-
步驟 2 − 如果堆疊已滿，則產生錯誤並退出
-
步驟 3 − 如果堆疊未滿，增加頂部指向下一個空的空間
-
步驟 4 − 添加數據元素堆疊位置，其中指向頂部
-
步驟 5 − 返回成功
如果鏈表用於實現堆疊，則在步驟3中，我們需要動態分配的空間。
演算法PUSH操作
一個簡單的演算法推送操作可推導如下 -
begin procedure push: stack, data
if stack is full
return null
endif
top ← top + 1
stack[top] ← data
end procedure
這個演算法用C語言來實現，是很容易的。請參見下麵的代碼 -
void push(int data) {
if(!isFull()) {
top = top + 1;
stack[top] = data;
}
else {
printf("Could not insert data, Stack is full.\n");
}
}
彈出操作
訪問內容要從堆疊取出，被稱為彈出操作。在數組實現POP()操作，數據元素實際上未被刪除，而是頂部遞減到一個較低的位置，棧指向下一個值。但在鏈表實現，pop()方法實際上刪除數據元素，並釋放記憶體空間。
彈出操作可能包括以下步驟 −
-
步驟 1 − 檢查堆疊是否為空
-
步驟 2 − 如果棧為空，則產生錯誤並退出
-
步驟 3 − 如果堆疊不空，訪問數據元素是在頂部指向
-
步驟 4 − 頂部值降低1
-
步驟 5 − 返回成功
POP演算法操作
一個簡單的演算法彈出操作可以如下 -
begin procedure pop: stack
if stack is empty
return null
endif
data ← stack[top]
top ← top - 1
return data
end procedure
這個演算法的 C語言實現，如下所示 -
int pop(int data) {
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
}
else {
printf("Could not retrieve data, Stack is empty.\n");
}
}
對於C編程語言的完整堆疊程式，請點擊