DSA 450 Notes

Problem Statement

Implement a Queue using two Stacks. The queue should support the following operations:

enqueue(x) / push(x): Add element x to the back of the queue
dequeue() / pop(): Remove and return the front element
front() / peek(): Return the front element without removing it
empty(): Return whether the queue is empty

Example:

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();   // returns 1
queue.pop();    // returns 1
queue.empty();  // returns false

Approach 1: Brute Force (Costly Enqueue)

Intuition

Make enqueue operation costly. When we enqueue, we first move all elements from stack1 to stack2, push the new element to stack1, then move all elements back. This ensures the oldest element is always on top of stack1.

Algorithm

For enqueue(x):
- Move all elements from s1 to s2
- Push x to s1
- Move all elements back from s2 to s1
For dequeue(): Simply pop from s1
For front(): Return top of s1
For empty(): Check if s1 is empty

java

import java.util.*;

class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;
    
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    
    // O(n) - Costly enqueue
    public void push(int x) {
        // Move all elements from s1 to s2
        while (!s1.isEmpty()) {
            s2.push(s1.pop());
        }
        
        // Push new element to s1
        s1.push(x);
        
        // Move all elements back to s1
        while (!s2.isEmpty()) {
            s1.push(s2.pop());
        }
    }
    
    // O(1)
    public int pop() {
        return s1.pop();
    }
    
    // O(1)
    public int peek() {
        return s1.peek();
    }
    
    // O(1)
    public boolean empty() {
        return s1.isEmpty();
    }
}

Complexity Analysis

Time Complexity: O(n) for enqueue, O(1) for dequeue, peek, empty
Space Complexity: O(n) - storing n elements across stacks

Approach 2: Optimal (Amortized O(1) - Lazy Transfer)

Intuition

Use two stacks: one for enqueue (input stack) and one for dequeue (output stack). Only transfer elements from input to output when output is empty and we need to dequeue. This gives amortized O(1) time for all operations.

Algorithm

For enqueue(x): Push to input stack (s1) - O(1)
For dequeue():
- If output stack (s2) is empty, transfer all from s1 to s2
- Pop from s2
For front(): Same as dequeue but peek instead of pop
For empty(): Both stacks must be empty

java

import java.util.*;

class MyQueue {
    private Stack<Integer> input;   // For enqueue
    private Stack<Integer> output;  // For dequeue
    
    public MyQueue() {
        input = new Stack<>();
        output = new Stack<>();
    }
    
    private void transfer() {
        while (!input.isEmpty()) {
            output.push(input.pop());
        }
    }
    
    // O(1)
    public void push(int x) {
        input.push(x);
    }
    
    // O(1) amortized
    public int pop() {
        if (output.isEmpty()) {
            transfer();
        }
        return output.pop();
    }
    
    // O(1) amortized
    public int peek() {
        if (output.isEmpty()) {
            transfer();
        }
        return output.peek();
    }
    
    // O(1)
    public boolean empty() {
        return input.isEmpty() && output.isEmpty();
    }
    
    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        
        queue.push(1);
        queue.push(2);
        queue.push(3);
        
        System.out.println("Pop: " + queue.pop());    // 1
        System.out.println("Pop: " + queue.pop());    // 2
        
        queue.push(4);
        
        System.out.println("Peek: " + queue.peek());  // 3
        System.out.println("Pop: " + queue.pop());    // 3
        System.out.println("Pop: " + queue.pop());    // 4
        System.out.println("Empty: " + queue.empty());  // true
    }
}

Complexity Analysis

Time Complexity: O(1) amortized for all operations
- Each element is moved at most twice (once to input, once to output)
Space Complexity: O(n) - storing n elements across stacks

Approach 3: Using Single Stack with Recursion

Intuition

Use recursion to simulate the reversal needed for queue operations. Pop all elements recursively, insert at bottom for enqueue, or get the bottom element for dequeue.

Algorithm

For enqueue: Insert element at the bottom of stack using recursion
For dequeue: Pop the top element (which is the front of queue)
Recursion acts as an implicit second stack

java

import java.util.*;

class MyQueue {
    private Stack<Integer> s;
    
    public MyQueue() {
        s = new Stack<>();
    }
    
    private void insertAtBottom(int x) {
        if (s.isEmpty()) {
            s.push(x);
            return;
        }
        
        int top = s.pop();
        insertAtBottom(x);
        s.push(top);
    }
    
    // O(n) - Uses recursion to insert at bottom
    public void push(int x) {
        insertAtBottom(x);
    }
    
    // O(1)
    public int pop() {
        return s.pop();
    }
    
    // O(1)
    public int peek() {
        return s.peek();
    }
    
    // O(1)
    public boolean empty() {
        return s.isEmpty();
    }
}

Complexity Analysis

Time Complexity: O(n) for push, O(1) for pop, peek, empty
Space Complexity: O(n) - recursion stack space

Key Takeaways

FIFO vs LIFO: Queue is FIFO, Stack is LIFO - need to reverse the order
Amortized Analysis: The two-stack approach gives O(1) amortized time
Lazy Evaluation: Only transfer elements when necessary (output stack empty)
Trade-offs: Choose between costly push or costly pop based on usage pattern
This is LeetCode #232 - Implement Queue using Stacks
Real-world use: Understanding data structure conversions and amortized complexity

Implement Queue using Stack

Problem Statement

Approach 1: Brute Force (Costly Enqueue)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (Amortized O(1) - Lazy Transfer)

Intuition

Algorithm

Complexity Analysis

Approach 3: Using Single Stack with Recursion

Intuition

Algorithm

Complexity Analysis

Key Takeaways