Stack Operations

A stack is a LIFO (Last-In-First-Out) data structure. You add and remove elements from the same end — the “top”. Think of a stack of plates.

Which Implementation to Use

	ArrayDeque	LinkedList	Legacy Stack
push/pop/peek	O(1)*	O(1)	O(1)*
Memory	Low	High	Medium
Thread-safe	No	No	Yes (but slow)
Recommendation	Use this	Acceptable	Avoid

*Amortized

Use ArrayDeque as your stack. The legacy Stack class extends Vector, carries synchronization overhead you don’t need, and exposes methods (like add(index, element)) that break stack semantics.

Stack with ArrayDeque (Recommended)

Deque<String> stack = new ArrayDeque<>();

stack.push("bottom");    // [bottom]
stack.push("middle");    // [middle, bottom]
stack.push("top");       // [top, middle, bottom]

stack.peek();            // "top" — look without removing
stack.pop();             // "top" — removes and returns
stack.pop();             // "middle"
stack.isEmpty();         // false
stack.size();            // 1

Drain a stack:

while (!stack.isEmpty()) {
    System.out.println(stack.pop());
}

Why Not the Legacy Stack Class

// Legacy — avoid in new code
Stack<String> stack = new Stack<>();
stack.push("a");
stack.push("b");

// Problem: inherits Vector methods that break LIFO semantics
stack.add(0, "inserted at bottom");  // this shouldn't be possible on a stack
stack.remove(1);                      // random removal from middle

The legacy Stack is synchronized, which adds overhead even in single-threaded code. For thread-safe stacks, use ConcurrentLinkedDeque or synchronize an ArrayDeque explicitly.

Common Stack Patterns

Balanced parentheses:

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

Reverse a collection:

Deque<Integer> stack = new ArrayDeque<>();
for (int num : list) stack.push(num);

List<Integer> reversed = new ArrayList<>();
while (!stack.isEmpty()) reversed.add(stack.pop());

Key Takeaway

Always declare your stack as Deque<T> and instantiate with ArrayDeque. This gives you the right interface (only stack operations visible) with the best performance.

Deque<String> stack = new ArrayDeque<>();  // correct
Stack<String> stack = new Stack<>();       // avoid