Java中的Stack通常是指Collection Framework中實現了List接口的類。它的工作原理是 Stack 數據結構,用於組織一種類型的內存。也可能是內存中保存數據的部分,在本文中我們將首先關注Stack類,考慮它的方法並舉例說明。但是我們也會講到Stack這樣的數據結構以及它的用途。

什麼是堆棧數據結構

首先,讓我們快速了解一下堆棧數據結構是什麼。它是一種基於後進先出 (LIFO) 原則的線性數據結構。這是一種反隊列。想像一副紙牌或盒子裡的一疊書。你先放進書堆的書在最下面,我們首先要從盒子裡拿出來的書是最上面的那本書——也就是最後進盒子的那本書。這裡有一張gif圖片來演示這個原理。 Java 堆棧 - 1這裡發生了什麼?我們有一個燒瓶,一次只能擊中一個球。燒瓶中的第一個是橙色球,然後是紫色,最後是綠色(我向那些知道這些顏色更準確名稱的人道歉)。然而,為了從燒瓶堆中提取橙色球,我們需要首先提取最後到達那裡的球(綠色那個),然後是倒數第二個(但在提取時它是最後一個)一)。Java 或其他編程中的堆棧數據結構有兩個最重要的操作,即pushpop。push 操作將一個元素插入棧中,pop 操作從棧頂移除一個元素。

Stack數據結構是做什麼用的?

堆棧最重要的用途之一是組織子程序調用。堆棧上的調用點存儲子程序終止後的返回地址(可能還有傳遞的參數)。對於子例程的每個嵌套(包括遞歸)調用,新的返回地址都會添加到堆棧中。隨著子程序的每個返回操作(返回),返回地址從堆棧中刪除,控制權轉移給它。此應用程序對於編程非常重要,以至於在大多數處理器中,返回堆棧是在指令集中的硬件中實現的。然而,在其他情況下,堆棧必須在更通用的數據結構上建模。

集合框架的 Java Stack 類

在 Java 中,Stack類是 Collection 框架中的一個類,它實現了 List 接口並擴展了 Vector 類。它還實現接口 Collection、Iterable、Cloneable、Serializable。正如您可能已經猜到的那樣,此類代表對象的後進先出堆棧。這裡是調用了Stack類的構造函數,也就是創建了這個類的一個對象。

Stack<E> stack = new Stack<E>();
其中E是對象的類型。

Java 堆棧方法

該類只有一個默認構造函數和Vector類的所有方法。另外,Stack有自己的 5 個方法:
  • boolean empty()方法檢查堆棧是否為空。如果堆棧為空則返回true ,否則返回false 。

  • Object peek()方法返回位於堆棧頂部的元素。

  • Object pop()方法返回位於棧頂的元素並將其移除。

  • Object push(Object element)方法將指定的元素添加到棧頂。

  • int search(Object element)該方法在堆棧中搜索指定元素。如果找到所需元素,則返回其與頂部(序列號)的“距離”。如果未找到該元素,則返回 -1。

堆棧代碼示例

讓我們創建一個像上面的 gif 圖片一樣工作的程序示例。我們將把三個“球”,橙色、紫色和綠色,放在堆棧上。讓我們檢查堆棧是否為空。然後,我們將從堆棧中提取球,直到堆棧為空。

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.push("Orange Ball");
           myStack.push("Violet Ball");
           myStack.push("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }
這是該程序的輸出:
我的堆棧是空的嗎?堆棧中的真實元素:[橙色球、紫色球、綠色球] 我的堆棧是空的嗎?false 堆棧中的元素:[Orange Ball, Violet Ball] 我的堆棧是空的嗎?false 堆棧中的元素:[橙色球] 我的堆棧是空的嗎?false 堆棧中的元素:[] 我的堆棧是空的嗎?真的
由於Stack繼承自Vector類並實現了List接口,因此Stack除了對這種數據結構有經典的push和pop操作,用於添加和提取元素外,還有標準的list結構add()remove()操作。在我們的示例中,可以使用add()方法以相同的方式實現添加元素。但是,您可以僅對指定的元素 使用remove()進行提取,這對堆棧數據結構沒有意義。

import java.util.Stack;

public class myStackTest2 {

       public static void main(String[] args)
       {

           Stack myStack= new Stack<>();

           System.out.println("Is my stack empty? " + myStack.empty());
// pushing elements into stack
           myStack.add("Orange Ball");
           myStack.add("Violet Ball");
           myStack.add("Green Ball");

//prints elements of the stack
           System.out.println("Elements in Stack: " + myStack);
           System.out.println("Is my stack empty? " + myStack.empty());
           while (!myStack.isEmpty()) {
               myStack.pop();
               System.out.println("Elements in Stack: " + myStack);
               System.out.println("Is my stack empty? " + myStack.empty());
           }
       }
   }
當然,程序工作的結果將完全相同。

你自己的 Stack 實現怎麼樣?

您可以使用數組或鍊錶類在 Java 中創建自己的堆棧數據結構。在第一種情況下,分配了一個連續的單元格數組來存儲內存中的值,這些值在需要時使用。在第二種情況下,對於堆棧的每個元素,一個內存塊是有序的,足以存儲值和對堆棧的前一個和下一個元素的引用。基於數組的實現更簡單、更高效且內存效率更高,但它需要事先了解堆棧大小限制,並可能導致難以發現的錯誤。基於列表的實現更健壯但效率較低。讓我們做一個簡單的基於數組的堆棧實現。它將包括功能。
  • push — 一種確保添加元素​​(在頂部位置)的方法

  • pop — 一種將提供元素移除的方法(從頂部位置)

  • readTop — 一種將返回位於頂部的元素的值的方法

  • sEmpty — 一種檢查堆棧是否為空的方法

  • isFull — 一種檢查我們存儲堆棧的數組是否未滿的方法


import java.util.Arrays;

public class MyStack {

   private int maxSize;
   private String[] stackArray;
   private int top;

   public MyStack(int size) {
       this.maxSize = size;
       stackArray = new String[maxSize];
       top = -1;
   }

   public String push (String element) {
       return stackArray[++top] = element;
      
   }

   public String pop (String element) {

       if (isEmpty())
       {
           System.out.println("Underflow\nProgram Terminated");
           System.exit(-1);
       }

       System.out.println("Removing " + readTop());
      
       return stackArray[top--];

   }

   public String readTop() {
       return stackArray[top];

   }

   public boolean isEmpty() {
       return (top ==  -1);
   }

   public boolean isFull() {
       return (top == maxSize - 1);
   }

   public void printStack(){
       System.out.println(Arrays.toString(stackArray));
   }
}
現在讓我們根據我們的堆棧實現一個包含三個球的示例:

public class myStackTest {
   public static void main(String[] args) {
       MyStack  myStack = new MyStack(3);
       System.out.println("Is my stack empty? " + myStack.isEmpty());

       myStack.push("Orange Ball");
       myStack.push("Violet Ball");
       myStack.push("Green Ball");

      myStack.printStack();

       System.out.println("Is my stack empty? " + myStack.isEmpty());
       while (!myStack.isEmpty()) {
           myStack.pop(myStack.readTop());
           System.out.println("Is my stack empty? " + myStack.isEmpty());
       }
   }

}
輸出在這裡:
我的堆棧是空的嗎?true [Orange Ball, Violet Ball, Green Ball] 我的籌碼是空的嗎?false Removing Green Ball 我的籌碼是空的嗎?false Removing Violet Ball 我的籌碼是空的嗎?false Removing Orange Ball 我的籌碼是空的嗎?真的
如果仔細觀察,top 變量實際上包含最後一個元素的索引,並且對該對象的引用保留在數組中。所以這個實現需要一些改進。想想最簡單的方法來做到這一點。

我們應該使用 Java Stack 嗎?

事實上,Java Stack與其Vector父類一樣,是一個遺留類。相反,通常使用ArrayList類。ArrayList不同步,而Vector是同步的。這意味著對於Vector,一次只有一個線程可以訪問代碼,而ArrayList可以使用多個線程。此外,ArrayList更高效、更快速。所以你很可能只會在遺留代碼中看到這個類。但是Stack數據結構在編程中使用的非常頻繁。