Java Stack Handbook

1. Quick Summary

The Stack class represents a Last-In-First-Out (LIFO) stack of objects. It extends class Vector, which means it is synchronized (thread-safe) but generally slower than modern alternatives.

• Package: java.util.Stack

• Key Concept: The last item you put in is the first item you take out.

• Status: Considered "Legacy" (but still widely used in Competitive Programming for convenience).

2. The Modern Alternative (Important)

Java documentation explicitly recommends using the Deque interface instead of Stack for new code.

Why? Stack is synchronized (locking overhead) and extends Vector (legacy). ArrayDeque is faster and not thread-safe.

// LEGACY WAY (Slower, Thread-safe)
Stack<String> stack = new Stack<>();

// MODERN WAY (Faster, Preferred)
Deque<String> stack = new ArrayDeque<>();

3. Essential Methods Cheat Sheet

4. Stack vs. ArrayDeque

5. Common Use Cases

1. Undo Mechanisms: Storing previous states (like Memento).

2. Backtracking Algorithms: Pathfinding (DFS), Solving Mazes.

3. Parsing: Syntax checking (Balanced Parentheses), Expression Evaluation (Postfix/Prefix).

Examples of implementation

​
import java.util.Stack;
import java.util.Deque;
import java.util.ArrayDeque;
/**
 * A comprehensive demonstration of Stack usages.
 * Includes:
 * 1. The Legacy Stack class usage.
 * 2. The Modern "Deque" alternative.
 * 3. A practical algorithm: Balanced Parentheses Checker.
 */
public class StackExamples {
 public static void main(String[] args) {
        System.out.println("=== 1. Legacy Stack (java.util.Stack) ===");
        demonstrateLegacyStack();
        System.out.println("\n=== 2. Modern Stack (java.util.ArrayDeque) ===");
        demonstrateModernStack();
        System.out.println("\n=== 3. Practical Example: Balanced Parentheses ===");
        String expr = "{[()]}";
        System.out.println("Expression: " + expr + " -> Balanced? " + isBalanced(expr));
 
        String badExpr = "{[(])}";
        System.out.println("Expression: " + badExpr + " -> Balanced? " + isBalanced(badExpr));
 }
 /**
     * Pattern 1: Using the classic java.util.Stack class.
     * Note: This class is synchronized (thread-safe).
     */
 private static void demonstrateLegacyStack() {
        Stack<String> books = new Stack<>();
 // 1. Push
        books.push("Harry Potter");
        books.push("Lord of the Rings");
        books.push("The Hobbit");
 // 2. Peek (Look without removing)
        System.out.println("Top book: " + books.peek()); // The Hobbit
 // 3. Search (1-based index from TOP)
 // "The Hobbit" is at 1, "Harry Potter" is at 3
 int pos = books.search("Harry Potter");
        System.out.println("Harry Potter is at position from top: " + pos);
 // 4. Pop (Remove)
 while (!books.empty()) {
            System.out.println("Popped: " + books.pop());
 }
 }
 /**
     * Pattern 2: Using ArrayDeque as a Stack.
     * This is preferred for single-threaded applications due to better performance.
     */
 private static void demonstrateModernStack() {
 // Deque stands for "Double Ended Queue"
        Deque<Integer> numbers = new ArrayDeque<>();
        numbers.push(10);
        numbers.push(20);
        numbers.push(30);
        System.out.println("Top number: " + numbers.peek());
 // Note: Deque uses isEmpty(), Stack uses empty()
 while (!numbers.isEmpty()) {
            System.out.println("Popped: " + numbers.pop());
 }
 }
 /**
     * Pattern 3: A classic interview problem using a Stack.
     * Check if parentheses are balanced: () {} []
     */
 private static boolean isBalanced(String expression) {
 // Use Deque for performance
        Deque<Character> stack = new ArrayDeque<>();
 for (char c : expression.toCharArray()) {
 // If opening brace, push to stack
 if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
 } 
 // If closing brace, check stack
 else if (c == ')' || c == '}' || c == ']') {
 if (stack.isEmpty()) return false;
 
 char lastOpen = stack.pop();
 if (!isMatchingPair(lastOpen, c)) {
 return false;
 }
 }
 }
 // If stack is empty, all braces were matched
 return stack.isEmpty();
 }
 private static boolean isMatchingPair(char open, char close) {
 return (open == '(' && close == ')') ||
 (open == '{' && close == '}') ||
 (open == '[' && close == ']');
 }
}