Stacks

Written Explanation

The three operations

Worked trace:

push(1)        stack (top on the left): 1
push(2)        stack: 2 1
pop() -> 2     stack: 1
peek() -> 1    stack: 1   (unchanged)

The last item in (2) was the first out. That is LIFO: last in, first out.

Java: use ArrayDeque

The JDK documentation for the Deque interface says deques can be used as LIFO stacks, and that this interface should be used in preference to the legacy Stack class. It maps the stack operations to push, pop, and peek. ArrayDeque is the usual implementation, and its documentation says it is likely to be faster than Stack when used as a stack.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop());    // 2
System.out.println(stack.peek());   // 1

Declare the variable as Deque<Integer> (the interface) and create an ArrayDeque. This follows the habit from the Collections module: code against the interface, choose the implementation in one place.

Two behaviors on an empty stack, which you must know:

• pop() throws NoSuchElementException.
• peek() returns null (it does not throw).

Also, ArrayDeque refuses null items: push(null) throws NullPointerException. That is why peek() can use null to mean "empty" without ambiguity.

Why not java.util.Stack?

Stack is a legacy class from the earliest versions of Java. It is built on Vector, which was designed so that its methods are synchronized, and it exposes list operations such as get(i) that break the "only touch the top" idea. The Deque documentation steers you away from it. In new code, use ArrayDeque.

Implementing a stack yourself

An array stack is an array plus size where the top is data[size - 1]; push is a dynamic-array append (Lesson 2) and pop removes the last item, so both are O(1) (push is amortized). A linked stack is a linked list where push is addFirst and pop is removeFirst (Lesson 3), so both are O(1) worst case. The lab asks you to build one of them.

T pop() {
    if (size == 0) throw new NoSuchElementException("stack is empty");
    T top = (T) data[--size];
    data[size] = null;      // let the removed object be collected
    return top;
}

Problems that are secretly stacks

• Undo: the last action is the first undone.
• Back button: the last page visited is the first you return to.
• The call stack: when a() calls b(), b must finish first. In BEG-038 you saw the stack of frames; StackOverflowError happens when it grows too deep.
• Matching brackets and nested structures: the most recently opened bracket must be closed first.
• Backtracking: try a path, and if it fails go back to the previous choice.

Bracket matching

Idea for "{[()]}": scan left to right.

1. On an opener (, [, {: push it.
2. On a closer: if the stack is empty, it is unbalanced; else pop and check that the popped opener matches this closer.
3. At the end the stack must be empty; leftovers are unclosed openers.

static boolean balanced(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stack.isEmpty()) return false;
            char open = stack.pop();
            if ((c == ')' && open != '(') || (c == ']' && open != '[')
                    || (c == '}' && open != '{')) return false;
        }
    }
    return stack.isEmpty();
}

One pass, O(1) per character, so O(n) overall. Deque<Character> works because char is boxed to Character automatically.