Q6: How do you implement a Queue using two Stacks (and analyze amortized time complexity)?

Maintain two stacks: inputStack and outputStack.

enqueue(x): Push x onto inputStack ($O(1)$).
dequeue(): If outputStack is empty, pop all elements from inputStack and push them onto outputStack (reversing their order). Pop top of outputStack ($O(1)$ amortized).

Queue Using Stacks Implementation

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

public class MyQueue {
    private final Deque<Integer> input = new ArrayDeque<>();
    private final Deque<Integer> output = new ArrayDeque<>();

    public void push(int x) {
        input.push(x);
    }
    public int pop() {
        peek();
        return output.pop();
    }
    public int peek() {
        if (output.isEmpty()) {
            while (!input.isEmpty()) {
                output.push(input.pop());
            }
        }
        return output.peek();
    }
    public boolean empty() {
        return input.isEmpty() && output.isEmpty();
    }
}

💡 Transfers items from input to output stack on demand to establish FIFO queue order.

Key Takeaways

inputStack accepts fresh incoming items.
outputStack provides FIFO ordering with amortized $O(1)$ operations.

Knowledge Check

What is the amortized time complexity of the pop() method in a queue built using two stacks?

Q6: How do you implement a Queue using two Stacks (and analyze amortized time complexity)?

STAY UPDATED WITH BYTES!