Java实现堆栈的方法

如何用 Java 自己实现堆栈——以四种不同的方式：

作为ArrayDeque的包装器(在本文中)。

使用数组

使用链表

使用队列

让我们从一个界面开始……

栈接口

首先，我们创建一个Stack界面。它只包含堆栈应该提供的那些方法，即：

push()– 将元素添加到堆栈

pop()– 从栈顶移除元素

peek()– 查看顶部堆栈元素而不删除它

isEmpty()– 检查堆栈是否为空(此方法可选)

以下代码显示了接口(GitHub 存储库中的类Stack )：

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

此时决定将 for和pop()throw peek()aNoSuchElementException放在空堆栈上，就像Deque's add//方法所做的那样。removeget

或者，也可以 return Optional。该决定取决于调用pop()和peek()在空堆栈上是异常(然后您应该抛出异常)或常规控制流(然后您应该返回一个Optional)的程度。

你不应该做的是返回null一个空堆栈。

使用 ArrayDeque 实现堆栈

我们的第一个实现包含一个围绕(非线程安全的)双端队列实现的适配器ArrayDeque。适配器转发堆栈方法如下：

Stack.push()→ArrayDeque.addFirst()

Stack.pop()→ArrayDeque.removeFirst()

Stack.peek()→ArrayDeque.getFirst()

Stack.isEmpty()→ArrayDeque.isEmpty()

首先，这是一个表示适配器模式的类图：

这是适配器的实现(GitHub 存储库中的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。

设计的测试代码可以毫不费力地处理额外的 Stack 实现(通过调用runDemo()其他Stack类的实例)。

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);
    }
  }
}

通过上述介绍，相信大家对堆栈已经有所了解，如果大家对此比较感兴趣，想了解更多相关知识，不妨来关注一下极悦的Java堆栈教程，里面有更丰富的知识等着大家去学习，希望对大家能够有所帮助哦。