javadata-structuresinterfacestack

Java interface for stack operations


I have in mind a method that takes as an argument a collection that supports just the stack operations push and pop. What is the most appropriate interface for this?

public void foo(WhatShouldThisTypeBe<String> stack) {
    stack.push(bar());
    ...;
    String xyz = stack.pop();
}
    

My thoughts are:

  1. I could make my method take a java.util.Stack but that is a legacy class, with unwanted synchronization overhead, and shouldn't be used in 2023.

  2. I could make it take a List (which supports the equivalent operations addLast() and removeLast()) but that would put unnecessary demands on the concrete type, such as the ability to take the nth element.

  3. I could make it take a Deque but again that would put unnecessary demands on the concrete type, such as support for the Queue operations add and remove which are not required.

Is there a Java interface that suits stack operations more precisely than any of the above?


Solution

  • SequencedCollection probably steers closest to what you're looking for; it has the obvious downside of not existing prior to JDK21, at which point Deque is probably the closest you want, but, as you found, it adds a little too much.

    Crucially for you, ArrayList does implement SequencedCollection.

    Failing all these things, there really is no option. You're presumably looking for some type that both ArrayDeque as well as ArrayList implement, as 2 somewhat arbitrarily chosen types that can trivially support fast 'add at end' and 'remove last' operations which is all you really need. The only one that is halfway relevant is Collection, but it does not offer 'remove from end', thus, cannot be used here.

    Hence, if requiring JDK21 isn't an option, then you're either stuck making multiple methods (one that takes any Deque, one that takes an ArrayList for example), making wrappers (make your own interface, then write methods that wrap types well known to support it into an object that implements this interface):

    public interface Stackish<E> {
      void push(E elem);
      E pop() throws NoSuchElementException;
    
      public static <E> Stackish<E> of(ArrayList<E> list) {
        return new Stackish<E>() {
          @Override public void push(E elem) {
            list.add(elem);
          }
    
          @Override public E pop() throws NoSuchElementException {
            try {
              return list.remove(list.size() - 1);
            } catch (IndexOutOfBoundsException e) {
              throw new NoSuchElementException();
            }
        };
      }
    }
    

    This would have the rather obvious annoying factor that users of your library need to wrap their collections.