如何使用陣列和泛型在 Java 中實現棧？

---

Java 透過利用陣列和泛型來實現棧。這建立了一個多功能且可重用的資料結構，其操作原理是後進先出 (LIFO)。在這個原理中，元素從頂部新增和移除。透過使用陣列作為其基礎，它確保了有效的記憶體分配和訪問。此外，透過整合泛型，棧能夠容納不同型別的元素，增強了其多功能性。

實現涉及定義一個包含泛型型別引數的 Stack 類。它包括基本方法，如 push()、pop()、peek() 和 isEmpty()。處理邊緣情況，如棧溢位和棧下溢，對於確保無縫功能也至關重要。此實現使開發人員能夠建立能夠容納 Java 中任何型別元素的棧。

Java 中的棧

在 Java 中，棧是一個重要的資料結構，其操作原理是後進先出 (LIFO)。它表示元素的集合，其中最近新增的元素在移除時優先。Java 中的 Stack 類提供了多種有效操作元素的方法。例如，push 方法允許您將元素新增到棧的頂部，而 pop 則移除並返回最頂部的元素。此外，peek 使您能夠檢索最頂部的元素而不將其移除，而 isEmpty 則檢查棧是否為空。

import java.util.Stack;

Stack<Type> stack = new Stack<>();
stack.push(element); // Adds 'element' to the top of the stack
Type topElement = stack.pop(); // Removes and returns the top element
Type peekElement = stack.peek(); // Retrieves the top element without removing it
boolean isEmpty = stack.isEmpty(); // Checks if the stack is empty

方法

有不同的方法可以使用陣列和泛型在 Java 中實現棧，我們將深入探討這兩種方法。

• 使用陣列實現棧

• 使用泛型實現棧

使用陣列實現棧

在使用陣列在 Java 中實現棧時，會建立一個遵循後進先出 (LIFO) 原則的資料結構。在這種方法中，元素儲存在陣列中，而 top 變數用於跟蹤表示棧中頂部元素的索引。

棧類通常包含幾種方法。這些方法包括 push()，用於將元素新增到棧的頂部；pop()，用於移除並檢索最頂部的元素；peek()，允許您檢視最頂部的元素而不將其移除；以及 isEmpty()，用於檢查棧是否為空。

演算法

• 建立一個數組來儲存棧的元素。

• 將名為“top”的變數初始化為 -1，表示空棧。

• 要將元素推入棧中

• 檢查棧是否已滿 (top == array.length - 1)。

• 如果棧未滿，則將“top”變數加 1，並將元素賦值給 array[top]。

• 要從棧中彈出元素

• 檢查棧是否為空 (top == -1)。

• 如果棧不為空，則從 array[top] 中檢索元素，並將“top”變數減 1。

示例

public class Stack {
   private int[] array;
   private int top;
   
   public Stack(int capacity) {
      array = new int[capacity];
      top = -1;
   }
   
   public void push(int element) {
      if (top == array.length - 1) {
         System.out.println("Stack is full. Cannot push element.");
      } else {
         top++;
         array[top] = element;
         System.out.println("Pushed element: " + element);
      }
   }
   
   public int pop() {
      if (top == -1) {
         System.out.println("Stack is empty. Cannot pop element.");
         return -1;
      } else {
         int poppedElement = array[top];
         top--;
         System.out.println("Popped element: " + poppedElement);
         return poppedElement;
      }
   }
   
   public int peek() {
      if (top == -1) {
         System.out.println("Stack is empty. No element to peek.");
         return -1;
      } else {
         System.out.println("Peeked element: " + array[top]);
         return array[top];
      }
   }
   
   public boolean isEmpty() {
      return (top == -1);
   }
   
   public static void main(String[] args) {
      Stack stack = new Stack(5);
      
      stack.push(10);
      stack.push(20);
      stack.push(30);
      
      stack.pop();
      
      stack.push(40);
      stack.push(50);
      
      stack.pop();
      stack.pop();
      stack.pop();
      stack.pop();
   }
}

輸出

Pushed element: 10
Pushed element: 20
Pushed element: 30
Popped element: 30
Pushed element: 40
Pushed element: 50
Popped element: 50
Popped element: 40
Popped element: 20
Popped element: 10

使用泛型實現棧

使用泛型實現的棧是一個通用的資料結構。它允許以後進先出 (LIFO) 的方式儲存和檢索元素，提供處理各種資料型別的靈活性。透過利用泛型，這個適應性強的棧成為一個能夠容納任何型別元素的高效容器，使其用途廣泛且可重複使用。

演算法

• 一個名為 Stack 的泛型類被建立用於在棧中儲存元素。

• 在 Stack 類內部，有一個私有陣列或連結串列來儲存這些元素。

• 棧使用一個建構函式初始化，該建構函式分配必要的記憶體。

• 要將元素新增到棧的頂部，實現了 push(element: T) 方法，該方法會增加棧的大小並存儲元素。

• 類似地，實現了 pop(): T 方法，用於從棧中移除並返回頂部元素，同時減小其大小。

• peek(): T 方法允許檢索頂部元素而不將其移除。

• 此外，isEmpty(): boolean 方法檢查棧是否為空，而 size(): number 返回當前棧中包含多少個元素。

示例

import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;

public class Stack<T> {
   private List<T> stack;

   public Stack() {
      stack = new ArrayList<>();
   }

   public void push(T element) {
      stack.add(element);
   }

   public T pop() {
      if (isEmpty()) {
         throw new EmptyStackException();
      }
      return stack.remove(stack.size() - 1);
   }

   public T peek() {
      if (isEmpty()) {
         throw new EmptyStackException();
      }
      return stack.get(stack.size() - 1);
   }

   public boolean isEmpty() {
      return stack.isEmpty();
   }

   public int size() {
      return stack.size();
   }

   public void clear() {
      stack.clear();
   }

   public static void main(String[] args) {
      Stack<Integer> stack = new Stack<>();

      stack.push(1);
      stack.push(2);
      stack.push(3);

      System.out.println("Stack size: " + stack.size());
      System.out.println("Top element: " + stack.peek());

      while (!stack.isEmpty()) {
         System.out.println("Popped element: " + stack.pop());
      }
   }
}

輸出

Stack size: 3
Top element: 3
Popped element: 3
Popped element: 2
Popped element: 1

結論

總之，在 Java 中實現棧時使用陣列和泛型具有通用性和型別安全性的優勢。透過整合泛型，開發人員能夠建立一個名為“Stack”的泛型類，該類可以容納任何型別的元素，從而增強了實現的靈活性。這種方法確保了棧資料結構能夠適應各種場景，同時保持嚴格的型別約束。

棧類使用型別為 T[] 的陣列來儲存元素，並使用一個名為“top”的整型變數來跟蹤最頂部的元素。它提供了 push、pop、peek 和 isEmpty 等基本方法，確保了高效的棧操作。

開發人員可以使用此實現來為特定型別建立自定義棧，同時受益於型別安全性的優勢。透過利用陣列和泛型，可以在 Java 中實現一個健壯且高效的棧資料結構。