資料結構和演算法教學 » 堆疊

堆疊

堆疊是一個抽象資料型別(ADT)，在大多數程式設計語言中常用。它被命名堆，因為它就像一個現實世界的堆，例如 - 撲克牌板或堆等。

Stack Example

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

這一特點使它成為後進先出的資料結構。 LIFO表示後進先出。這裡放置（插入或新增）最後元素，在第一次存取。在堆的術語中，插入操作被稱為PUSH操作，刪除操作稱為POP操作。

堆疊表示

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

Stack Representation

堆疊可通過陣列，結構和連結串列來實現。堆疊可以是固定大小或它可動態調整。在這裡，我們要實現使用堆疊陣列，這使用的是一個固定大小的堆疊實現。

基本操作

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

  • 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 Push Operation

如果連結串列用於實現堆疊，則在步驟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 Operation

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程式設計語言的完整堆疊程式，請點選