Topic 39 of 79

Stack

Q: How would you implement a Stack using only Queues?

Use two Queues (q1 and q2). For `push(x)`, enqueue `x` to q2. Then dequeue all elements from q1 and enqueue them to q2. Finally, swap the names of q1 and q2. This makes `push` O(N) and `pop` O(1). Alternatively, you can do it with one Queue by enqueuing `x`, then dequeuing and re-enqueuing all the other elements behind it.

Overview

A Stack is a linear data structure that strictly follows the LIFO (Last-In, First-Out) principle. Think of it like a physical stack of plates in a cafeteria: you can only add a new plate to the top of the stack, and you can only take a plate off the top of the stack. The last plate placed is the first one removed.

The core operations of a Stack are Push (add to top), Pop (remove from top), and Peek (look at the top without removing). All three operations must execute in strict O(1) time.

Stacks are not just abstract concepts; they are the fundamental mechanism powering modern computing. Every time a Java method is called, a new 'frame' is pushed onto the JVM's Call Stack. When the method returns, its frame is popped off. Stacks are also the core data structure used in Depth-First Search (DFS) algorithms, expression evaluation, and undo/redo mechanics.

Syntax

While Java has a java.util.Stack class, it extends Vector and is synchronized, making it unnecessarily slow. The official Java documentation recommends using ArrayDeque when you need a stack.

Using Java's Deque as a Stack

java

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

public class Main {
    public static void main(String[] args) {
        // NOTE: In modern Java, ArrayDeque is preferred over the legacy Stack class!
        Deque<String> stack = new ArrayDeque<>();
        
        // 1. Push (Add to top) - O(1)
        stack.push("First");
        stack.push("Second");
        stack.push("Third");
        
        // 2. Peek (View top without removing) - O(1)
        System.out.println("Top is: " + stack.peek()); // "Third"
        
        // 3. Pop (Remove and return top) - O(1)
        String removed = stack.pop(); 
        System.out.println("Removed: " + removed); // "Third"
        
        // 4. Check if empty
        while (!stack.isEmpty()) {
            System.out.println("Popping: " + stack.pop());
        }
        // Output: "Second", then "First"
    }
}

Common Pitfalls

Using the legacy java.util.Stack class. It was introduced in Java 1.0 and every single method is synchronized, causing thread-locking overhead even in single-threaded apps. Always use Deque<T> stack = new ArrayDeque<>() instead.
Calling pop() or peek() on an empty stack. This will throw a NoSuchElementException (or EmptyStackException). Always wrap pops inside a while(!stack.isEmpty()) check, or explicitly check isEmpty() before peeking.
Confusing add() with push(). While ArrayDeque supports both, push() adds to the front (top) of the deque, while add() adds to the back (tail). Mixing them up will turn your Stack into a Queue!

Interview Questions

How would you implement a Stack using only Queues?

Use two Queues (q1 and q2). For push(x), enqueue x to q2. Then dequeue all elements from q1 and enqueue them to q2. Finally, swap the names of q1 and q2. This makes push O(N) and pop O(1). Alternatively, you can do it with one Queue by enqueuing x, then dequeuing and re-enqueuing all the other elements behind it.

What is a StackOverflowError in Java?

It occurs when the JVM's Call Stack exceeds its memory limit. Every method call pushes a frame (containing local variables and return addresses) to the call stack. If a recursive method lacks a base case, it will call itself infinitely, pushing frames until the memory allocated for the thread's stack is completely exhausted.

Why is an Array-backed Stack (like ArrayDeque) generally faster than a Linked-List-backed Stack?

Cache locality. Arrays store data contiguously in memory, which the CPU cache can pre-fetch highly efficiently. Linked List nodes are scattered across the heap, causing CPU cache misses. Additionally, Linked Lists have the overhead of instantiating a new Node object for every single push operation.

Real-World Example

Text editors use two Stacks to implement the Undo and Redo features. When you type, actions are pushed to the Undo stack. When you hit Ctrl+Z, the action is popped from the Undo stack and pushed to the Redo stack. If you type something new, the Redo stack is cleared.

example

java

Deque<String> undoStack = new ArrayDeque<>();
Deque<String> redoStack = new ArrayDeque<>();

public void typeText(String text) {
    undoStack.push(text);
    redoStack.clear(); // Typing clears redo history
}

public void undo() {
    if (!undoStack.isEmpty()) {
        String action = undoStack.pop();
        redoStack.push(action);
        // revert action in UI...
    }
}

public void redo() {
    if (!redoStack.isEmpty()) {
        String action = redoStack.pop();
        undoStack.push(action);
        // apply action in UI...
    }
}

Check Your Knowledge

Test your understanding of Stack with these quick questions.

Which principle governs how a Stack operates?

What is the recommended Java class to use when you need a Stack?

What is the time complexity of the `push()` and `pop()` operations?

Take Java Quiz

Overview

The core operations of a Stack are Push (add to top), Pop (remove from top), and Peek (look at the top without removing). All three operations must execute in strict O(1) time.

Syntax

While Java has a java.util.Stack class, it extends Vector and is synchronized, making it unnecessarily slow. The official Java documentation recommends using ArrayDeque when you need a stack.

Using Java's Deque as a Stack

java

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

public class Main {
    public static void main(String[] args) {
        // NOTE: In modern Java, ArrayDeque is preferred over the legacy Stack class!
        Deque<String> stack = new ArrayDeque<>();
        
        // 1. Push (Add to top) - O(1)
        stack.push("First");
        stack.push("Second");
        stack.push("Third");
        
        // 2. Peek (View top without removing) - O(1)
        System.out.println("Top is: " + stack.peek()); // "Third"
        
        // 3. Pop (Remove and return top) - O(1)
        String removed = stack.pop(); 
        System.out.println("Removed: " + removed); // "Third"
        
        // 4. Check if empty
        while (!stack.isEmpty()) {
            System.out.println("Popping: " + stack.pop());
        }
        // Output: "Second", then "First"
    }
}

Common Pitfalls

Using the legacy java.util.Stack class. It was introduced in Java 1.0 and every single method is synchronized, causing thread-locking overhead even in single-threaded apps. Always use Deque<T> stack = new ArrayDeque<>() instead.
Calling pop() or peek() on an empty stack. This will throw a NoSuchElementException (or EmptyStackException). Always wrap pops inside a while(!stack.isEmpty()) check, or explicitly check isEmpty() before peeking.
Confusing add() with push(). While ArrayDeque supports both, push() adds to the front (top) of the deque, while add() adds to the back (tail). Mixing them up will turn your Stack into a Queue!

Interview Questions

How would you implement a Stack using only Queues?

What is a StackOverflowError in Java?

Why is an Array-backed Stack (like ArrayDeque) generally faster than a Linked-List-backed Stack?

Real-World Example

example

java

Deque<String> undoStack = new ArrayDeque<>();
Deque<String> redoStack = new ArrayDeque<>();

public void typeText(String text) {
    undoStack.push(text);
    redoStack.clear(); // Typing clears redo history
}

public void undo() {
    if (!undoStack.isEmpty()) {
        String action = undoStack.pop();
        redoStack.push(action);
        // revert action in UI...
    }
}

public void redo() {
    if (!redoStack.isEmpty()) {
        String action = redoStack.pop();
        undoStack.push(action);
        // apply action in UI...
    }
}

Check Your Knowledge

Test your understanding of Stack with these quick questions.