1. Understanding the Problem

You are tasked with implementing a First-In-First-Out (FIFO) queue using only two Last-In-First-Out (LIFO) stacks. The implemented queue should support all the functions of a normal queue: push (insert at back), peek (get the front element), pop (remove the front element), and empty (check if empty).

The Core Constraint (The Trap):

A stack works like a stack of plates: the last plate you put on top is the first one you take off. A queue works like a line at a grocery store: the first person in line is the first one served. You must somehow reverse the order of elements using standard stack operations (push to top, pop from top) to simulate the grocery store line.

2. The Naive Approach: Transfer Every Time

The most intuitive way to solve this is to force the stack to keep the oldest element at the very top. To do this, every time a new element arrives (push), you move all existing elements from your primary stack to a secondary stack, put the new element at the bottom of the primary stack, and then move everything back.

Trade-off Analysis

While this accurately simulates a queue, it is highly inefficient for write-heavy applications:

• Time Complexity: O(N) for every push operation. If you have 1,000 elements, adding one more requires 2,000 stack movements. pop and peek are O(1).
• Space Complexity: O(N) to store the elements.

3. The Optimal Approach: Input and Output Stacks (Amortized O(1))

To pass a senior-level technical interview, we want to achieve an Amortized O(1) time complexity for all operations. Instead of constantly shifting elements back and forth, we can designate specific roles for our two stacks: one for Input (stack_in) and one for Output (stack_out).

Imagine a mailroom. Incoming packages are just tossed into a bin (the Input Stack). Only when the delivery driver arrives and demands the oldest packages do we take the entire bin and flip it upside down into the delivery truck (the Output Stack). Now, the oldest package is at the top of the truck, ready to go!

We only perform this "flipping" operation when the stack_out is completely empty. As long as stack_out has elements, we can just pop directly from it in O(1) time.

4. The Logic Step-by-Step

1. Initialization: Create two stacks, stack_in and stack_out.
2. Push: Simply push the new element onto stack_in. This is always O(1).
3. Pop / Peek:
   • Check if stack_out is empty.
   • If it is empty, pop every single element from stack_in and push it onto stack_out. This reverses their order, bringing the oldest element to the top.
   • If stack_out is not empty, do nothing to stack_in.
   • Return (or remove) the top element from stack_out.
4. Empty: The queue is empty only if both stack_in and stack_out are empty.

5. Complexity Analysis

• Time Complexity: O(1) for push and empty. Amortized O(1) for pop and peek. While moving elements from stack_in to stack_out takes O(N) time, this move happens rarely. Over a long sequence of operations, the average time per operation remains constant.
• Space Complexity: O(N) — We need to store all the elements in the stacks, where N is the number of elements currently in the queue.

6. Code Implementations

Expand the sections below to see the optimal Amortized O(1) "Two-Stack" implementations across different languages.

class MyQueue:

    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def push(self, x: int) -> None:
        self.stack_in.append(x)

    def pop(self) -> int:
        self.peek() # Ensure stack_out has the current oldest elements
        return self.stack_out.pop()

    def peek(self) -> int:
        # If stack_out is empty, transfer all elements from stack_in
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        return self.stack_out[-1]

    def empty(self) -> bool:
        return not self.stack_in and not self.stack_out

import java.util.Stack;

class MyQueue {
    private Stack<Integer> stackIn;
    private Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {
        peek(); // Ensure stackOut is populated
        return stackOut.pop();
    }
    
    public int peek() {
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.peek();
    }
    
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}

#include <stack>

class MyQueue {
private:
    std::stack<int> stack_in;
    std::stack<int> stack_out;

public:
    MyQueue() {}
    
    void push(int x) {
        stack_in.push(x);
    }
    
    int pop() {
        int top = peek(); // Ensure stack_out has the data
        stack_out.pop();
        return top;
    }
    
    int peek() {
        if (stack_out.empty()) {
            while (!stack_in.empty()) {
                stack_out.push(stack_in.top());
                stack_in.pop();
            }
        }
        return stack_out.top();
    }
    
    bool empty() {
        return stack_in.empty() && stack_out.empty();
    }
};

7. Conclusion: You Are Ready

Congratulations, you have successfully designed a complex data structure using basic building blocks! Understanding amortized time complexity and lazy data transfer (only moving data when absolutely necessary) is a hallmark of a mature engineer. This two-stack pattern teaches you that sometimes, holding off on a heavy operation until the last possible moment yields the best overall performance. Keep practicing these foundational design patterns, and you will confidently navigate any systems or data structure design interview!