The Deque ADT

Here is the deque ADT:

public interface Deque<T> {
  void addFirst(T item);
  void addLast(T item);
  void removeFirst();
  void removeLast();
  T getFirst();
  T getLast();
  boolean isEmpty();
}

The names say which end each operation uses. As with Stack and Queue, looking and removing are separate operations.

              ┌───────┬─────────────────┬───────┐
   addFirst → │ first │       ...       │ last  │ ← addLast
removeFirst ← │ item  │                 │ item  │ → removeLast
              └───────┴─────────────────┴───────┘
                  ↑                         ↑
              getFirst                   getLast

We said earlier that the interface has both stack-like and queue-like behavior, but it does not force you to pick one. The interface does not say that the first end is the top of a stack or the front of a queue.