如何用 Java 自己實(shí)現(xiàn)堆棧——以四種不同的方式：

作為ArrayDeque的包裝器(在本文中)。

使用數(shù)組

使用鏈表

使用隊(duì)列

讓我們從一個(gè)界面開(kāi)始……

棧接口

首先，我們創(chuàng)建一個(gè)Stack界面。它只包含堆棧應(yīng)該提供的那些方法，即：

push()– 將元素添加到堆棧

pop()– 從棧頂移除元素

peek()– 查看頂部堆棧元素而不刪除它

isEmpty()– 檢查堆棧是否為空(此方法可選)

以下代碼顯示了接口(GitHub 存儲(chǔ)庫(kù)中的類Stack )：

public interface Stack<E> {
  void push(E item);
  E pop();
  E peek();
  boolean isEmpty();
}

此時(shí)決定將 for和pop()throw peek()aNoSuchElementException放在空堆棧上，就像Deque's add//方法所做的那樣。removeget

或者，也可以 return Optional。該決定取決于調(diào)用pop()和peek()在空堆棧上是異常(然后您應(yīng)該拋出異常)或常規(guī)控制流(然后您應(yīng)該返回一個(gè)Optional)的程度。

你不應(yīng)該做的是返回null一個(gè)空堆棧。

使用 ArrayDeque 實(shí)現(xiàn)堆棧

我們的第一個(gè)實(shí)現(xiàn)包含一個(gè)圍繞(非線程安全的)雙端隊(duì)列實(shí)現(xiàn)的適配器ArrayDeque。適配器轉(zhuǎn)發(fā)堆棧方法如下：

Stack.push()→ArrayDeque.addFirst()

Stack.pop()→ArrayDeque.removeFirst()

Stack.peek()→ArrayDeque.getFirst()

Stack.isEmpty()→ArrayDeque.isEmpty()

首先，這是一個(gè)表示適配器模式的類圖：

這是適配器的實(shí)現(xiàn)(GitHub 存儲(chǔ)庫(kù)中的ArrayDequeStack類)：

public class ArrayDequeStack<E> implements Stack<E> {
  private final Deque<E> deque = new ArrayDeque<>();
  @Override
  public void push(E item) {
    deque.addFirst(item);
  }
  @Override
  public E pop() {
    return deque.removeFirst();
  }
  @Override
  public E peek() {
    return deque.getFirst();
  }
  @Override
  public boolean isEmpty() {
    return deque.isEmpty();
  }
}

以下示例程序( GitHub 中的StackDemo類)顯示了該類的示例用法ArrayDequeStack。

設(shè)計(jì)的測(cè)試代碼可以毫不費(fèi)力地處理額外的 Stack 實(shí)現(xiàn)(通過(guò)調(diào)用runDemo()其他Stack類的實(shí)例)。

public class StackDemo {
  public static void main(String[] args) {
    runDemo(new ArrayDequeStack<>());
  }
  private static void runDemo(Stack<Integer> stack) {
    System.out.println("-------- " + stack.getClass().getSimpleName() + " --------");
    stack.push(1);
    stack.push(2);
    stack.push(3);
    System.out.println("stack.peek() = " + stack.peek());
    System.out.println("stack.pop() = " + stack.pop());
    System.out.println("stack.pop() = " + stack.pop());
    System.out.println("stack.pop() = " + stack.pop());
    try {
      System.out.println("stack.pop() = " + stack.pop());
    } catch (Exception ex) {
      ex.printStackTrace(System.out);
    }
  }
}

通過(guò)上述介紹，相信大家對(duì)堆棧已經(jīng)有所了解，如果大家對(duì)此比較感興趣，想了解更多相關(guān)知識(shí)，不妨來(lái)關(guān)注一下動(dòng)力節(jié)點(diǎn)的Java堆棧教程，里面有更豐富的知識(shí)等著大家去學(xué)習(xí)，希望對(duì)大家能夠有所幫助哦。