Stack Implementation in Java

In the last part of the tutorial, "Stack class in Java", you learned why you should not use Java's Stack class (unnecessary operations like insertElementAt() and setElementAt(), missing interface, over-synchronized).

The alternative recommended by the JDK developers, Deque, also provides methods that don't belong in a stack, e.g. addLast() and removeLast().

The unnecessary operations contradict the Interface Segregation Principle (ISP), according to which an interface should contain only those methods that the user of that interface needs.

Therefore, in this and the following parts of this tutorial, I will show how to implement a stack yourself in Java – in four different ways:

• As a wrapper around an ArrayDeque (in this article).
• Using an array
• Using a linked list
• Using queues

Let's start with an interface…

Stack Interface

First, we create a Stack interface. It contains only those methods that a stack should offer, namely:

• push() – to add elements to the stack
• pop() – to remove elements from the top of the stack
• peek() – to view the top stack element without removing it
• isEmpty() – to check if the stack is empty (this method is optional)

The following code shows the interface (class Stack in the GitHub repo):

public interface Stack<E> {
  void push(E item);
  E pop();
  E peek();
  boolean isEmpty();
}Code language: Java (java)

I decided at this point for pop() and peek() to throw a NoSuchElementException on an empty stack, just like Deque's add/remove/get methods do.

Alternatively, one could also return Optional<E>. The decision depends on the extent to which calling pop() and peek() on an empty stack is an exception (then you should throw exceptions), or a regular control flow (then you should return an Optional).

What you should not do is return null on an empty stack.

Implementing a Stack with an ArrayDeque

Our first implementation consists of an adapter around the (non-thread-safe) deque implementation ArrayDeque. The adapter forwards the stack methods as follows:

• Stack.push() → ArrayDeque.addFirst()
• Stack.pop() → ArrayDeque.removeFirst()
• Stack.peek() → ArrayDeque.getFirst()
• Stack.isEmpty() → ArrayDeque.isEmpty()

First, here is a class diagram that represents the adapter pattern:

And here is the implementation of the adapter (class ArrayDequeStack in the GitHub repo):

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();
  }
}Code language: Java (java)

The following sample program (StackDemo class in GitHub) shows an example usage of the ArrayDequeStack class.

I have designed the test code to handle additional Stack implementations without much effort (by calling runDemo() on instances of other Stack classes).

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);
    }
  }
}Code language: Java (java)

Conclusion

With just a few lines of code, we implemented our own (non-thread-safe) stack class.

To implement a thread-safe stack, we can analogously put an adapter around a thread-safe deque – like ConcurrentLinkedDeque (non-blocking) or LinkedBlockingDeque (blocking).

In the next part of the tutorial, I will show you how to implement a stack with an array.

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.