Stack

TL;DR

• Stack represents a Last-In-First-Out (LIFO) stack of objects.
• In Java, the Stack class extends Vector, making it a legacy, synchronized class.
• Best Practice: Do not use the Stack class. Use Deque (like ArrayDeque) instead for stack operations.

Concept

A LIFO structure means the last item added to the stack is the first one removed (think of a stack of plates).

Standard stack operations:

• push(): Adds an item to the top.
• pop(): Removes and returns the top item.
• peek(): Returns the top item without removing it.

Why java.util.Stack is broken

Because Stack extends Vector, it inherits all of Vector’s methods. A stack is supposed to restrict access to only the top element. But because it extends Vector, you can do stack.insertElementAt(item, 2), completely violating the LIFO principle.

Examples

import java.util.Stack;
import java.util.ArrayDeque;
import java.util.Deque;

public class StackExample {
    public static void main(String[] args) {
        
        // --- THE OLD/BAD WAY (Legacy Stack) ---
        Stack<String> legacyStack = new Stack<>();
        legacyStack.push("A");
        legacyStack.push("B");
        System.out.println(legacyStack.pop()); // "B"
        
        // Violates Stack principles!
        legacyStack.add(0, "C"); 

        
        // --- THE MODERN/GOOD WAY (ArrayDeque) ---
        Deque<String> modernStack = new ArrayDeque<>();
        modernStack.push("X");
        modernStack.push("Y");
        
        System.out.println(modernStack.pop()); // "Y"
        System.out.println(modernStack.peek()); // "X"
    }
}

Interview Questions

Q: Why should you use ArrayDeque instead of Stack?
A: 1. Design Flaw: Stack extends Vector, inheriting index-based access which violates the LIFO principle.
2. Performance: Stack is synchronized (because Vector is), which adds unnecessary locking overhead in single-threaded scenarios. ArrayDeque is not synchronized and is significantly faster.

Q: If you need a thread-safe Stack, what should you use?
A: Instead of falling back to the legacy Stack class, you should use ConcurrentLinkedDeque (lock-free) or LinkedBlockingDeque (blocking) from the java.util.concurrent package, depending on your concurrency requirements.