Java堆棧

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

什麼是堆棧數據結構

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

這是該程序的輸出： 由於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());
       }
   }

}

輸出在這裡： 如果仔細觀察，top 變量實際上包含最後一個元素的索引，並且對該對象的引用保留在數組中。所以這個實現需要一些改進。想想最簡單的方法來做到這一點。

我們應該使用 Java Stack 嗎？

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