The Stack ADT

Here is the stack ADT:

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

It is a small interface, with only four methods. The push method adds an item to the top of the stack, and the pop method removes the top item. The top method returns the item at the top of the stack without removing it. The isEmpty method checks if the stack is empty.

Notice there is no operation to get an item at an index, and no way to add or remove anywhere except the top. This is the “limited access” we asked for in the previous section.

Also notice that pop does not return the removed item. This interface separates looking from removing: call top to see the top item, then pop to remove it. Giving each method a single job this way follows the single responsibility principle. Some implementations combine the two into a single method that removes and returns the top item; both designs are common.

A stack of items behaves like a plate dispenser in a cafeteria. You push a plate down onto the pile to add it, and the plate you take off is always the one on top. The names push and pop come from that.

It helps to picture the stack as a vertical pile of items. In the diagram below, each row is one item, and the rows are ordered by when they were added. Read it from the bottom up, in the order the items arrived:

┌─────────────────┐
│ nth item added  │ ← top
├─────────────────┤
│ ...             │
├─────────────────┤
│ 2nd item added  │
├─────────────────┤
│ 1st item added  │
└─────────────────┘

The item that arrived last sits at the top. The top is the only item the four operations can reach, so the item that leaves first is always the item that arrived last. That order is called last in, first out, or LIFO. It is the same order we saw with undo, where the most recent action is the first one reversed.