堆棧

堆棧是一個抽象數據類型(ADT),在大多數編程語言中常用。它被命名堆,因爲它就像一個現實世界的堆,例如 - 撲克牌板或堆等。

Stack

一個真實世界的堆棧允許保存操作僅在一端進行。例如,我們只可以把或從堆棧頂部取出存儲卡或板。同樣地,堆棧ADT允許僅在一端執行所有數據操作。在任何特定時間,我們只能訪問一個堆棧的頂部元素。

這一特點使它成爲後進先出的數據結構。 LIFO表示後進先出。這裏放置(插入或添加)最後元素,在第一次訪問。在堆的術語中,插入操作被稱爲PUSH操作,刪除操作稱爲POP操作。

堆棧表示

如下圖試圖描繪出堆棧及其操作 -

Stack

堆棧可通過數組,結構和鏈表來實現。堆棧可以是固定大小或它可動態調整。在這裏,我們要實現使用堆棧數組,這使用的是一個固定大小的堆棧實現。

基本操作

堆棧操作可能涉及初始化堆棧,使用它,然後去對其進行初始化。除了這些基本的東西,堆棧用於以下兩個主要的操作 -

  • 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 − 返回成功

Stack

如果鏈表用於實現堆棧,則在步驟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

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編程語言的完整堆棧程序,請點擊