4.2.3.1 - Stacks and their operations (Java)

LIFO and stack state

A stack gives access to the most recently added item that has not yet been removed.

An undo history stores the most recent action on top, so it is reversed first. Nested subroutine calls also return in reverse call order: a call stack holds frames containing return information and local state. A stack's ordering is useful whenever the latest unfinished operation must be handled first.

For a bounded Java array implementation, let top be the index of the current top item. Empty state is top = -1. With capacity 4, the live indices are 0 through top. Full state is top = 3, equal to data.length - 1. The values above top are irrelevant even if old data remains there.

The pop returns 9. An alternative convention might use a count or next-free index. Its boundary expressions differ, so read the given definition before tracing.

Push, pop and peek

Each operation changes only the state required by its contract.

final class IntStack {
    private final int[] data = new int[4];
    private int top = -1;
    boolean isEmpty() { return top == -1; }
    boolean isFull() { return top == data.length - 1; }
    void push(int value) {
        if (isFull()) throw new IllegalStateException("Full");
        top++;
        data[top] = value;
    }
    int pop() {
        if (isEmpty()) throw new IllegalStateException("Empty");
        int value = data[top];
        top--;
        return value;
    }
    int peek() {
        if (isEmpty()) throw new IllegalStateException("Empty");
        return data[top];
    }
}

Push first makes a new top position then stores the value there. Pop saves the current value before lowering top. Peek, also called top, returns the same value that pop would return but leaves the structure unchanged. With push 6, push 2, peek, pop, peek, the three returned values are 2, 2 and 6.

The checks precede array access or index changes. Otherwise a full push could corrupt top before failing, or an empty pop could access index -1. Increment/decrement shortcuts are valid only if their order has the same meaning as the expanded operations.