Java 資料結構教程

Java 資料結構 - 堆疊類

堆疊是一種抽象資料型別 (ADT)，在大多數程式語言中常用。它被稱為堆疊，因為它表現得像現實世界中的堆疊，例如——一副撲克牌或一堆盤子等。

現實世界的堆疊只允許在一端進行操作。例如，我們只能在堆疊頂部放置或移除卡片或盤子。同樣，堆疊 ADT 也只允許在一端進行所有資料操作。在任何給定時間，我們只能訪問堆疊的頂部元素。

此功能使其成為後進先出 (LIFO) 資料結構。LIFO 代表後進先出。這裡，最後放置（插入或新增）的元素首先被訪問。在堆疊術語中，插入操作稱為PUSH操作，刪除操作稱為POP操作。

堆疊表示

下圖描述了一個堆疊及其操作：

堆疊可以透過陣列、結構、指標和連結串列來實現。堆疊可以是固定大小的，也可以具有動態調整大小的功能。在這裡，我們將使用陣列來實現堆疊，這使得它成為一個固定大小的堆疊實現。

堆疊類

Stack 是 Vector 的一個子類，它實現了一個標準的後進先出堆疊。

Stack 只定義了預設建構函式，它建立一個空堆疊。Stack 包括 Vector 定義的所有方法，並添加了一些它自己的方法。

Stack( )

除了從其父類 Vector 繼承的方法外，Stack 還定義了以下方法：

序號	方法和描述
1	boolean empty() 測試此堆疊是否為空。如果堆疊為空，則返回 true；如果堆疊包含元素，則返回 false。
2	Object peek( ) 返回堆疊頂部的元素，但不將其移除。
3	Object pop( ) 返回堆疊頂部的元素，並在過程中將其移除。
4	Object push(Object element) 將元素壓入堆疊。元素也會被返回。
5	int search(Object element) 在堆疊中搜索元素。如果找到，則返回其距堆疊頂部的偏移量。否則，返回 -1。

示例

以下程式演示了此集合支援的幾種方法：

線上演示

import java.util.*;
public class StackDemo {
   static void showpush(Stack st, int a) {
      st.push(new Integer(a));
      System.out.println("push(" + a + ")");
      System.out.println("stack: " + st);
   }

   static void showpop(Stack st) {
      System.out.print("pop -> ");
      Integer a = (Integer) st.pop();
      System.out.println(a);
      System.out.println("stack: " + st);
   }

   public static void main(String args[]) {
      Stack st = new Stack();
      System.out.println("stack: " + st);
      showpush(st, 42);
      showpush(st, 66);
      showpush(st, 99);
      showpop(st);
      showpop(st);
      showpop(st);
      
      try {
         showpop(st);
      } catch (EmptyStackException e) {
         System.out.println("empty stack");
      }
   }
}

輸出

stack: [ ]
push(42)
stack: [42]
push(66)
stack: [42, 66]
push(99)
stack: [42, 66, 99]
pop -> 99
stack: [42, 66]
pop -> 66
stack: [42]
pop -> 42
stack: [ ]
pop -> empty stack

列印頁面