Code Implementation

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

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

    def pop(self) -> int:
        self.peek()
        return self.out_stack.pop()

    def peek(self) -> int:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack[-1]

    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack
      

class MyQueue {
private:
    stack<int> inStack, outStack;
public:
    MyQueue() {}

    void push(int x) {
        inStack.push(x);
    }
    
    int pop() {
        peek();
        int val = outStack.top();
        outStack.pop();
        return val;
    }
    
    int peek() {
        if (outStack.empty()) {
            while (!inStack.empty()) {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        return outStack.top();
    }
    
    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};
      

class MyQueue {
    private Stack<Integer> inStack = new Stack<>();
    private Stack<Integer> outStack = new Stack<>();

    public MyQueue() {}

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        peek();
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}
      

var MyQueue = function() {
    this.inStack = [];
    this.outStack = [];
};

MyQueue.prototype.push = function(x) {
    this.inStack.push(x);
};

MyQueue.prototype.pop = function() {
    this.peek();
    return this.outStack.pop();
};

MyQueue.prototype.peek = function() {
    if (this.outStack.length === 0) {
        while (this.inStack.length) {
            this.outStack.push(this.inStack.pop());
        }
    }
    return this.outStack[this.outStack.length - 1];
};

MyQueue.prototype.empty = function() {
    return this.inStack.length === 0 && this.outStack.length === 0;
};
      

Problem Description

The task is to implement a queue using only stack data structures. You must support the following operations:

• push(x): Add element x to the back of the queue.
• pop(): Removes the element from the front of the queue and returns it.
• peek(): Returns the element at the front of the queue without removing it.
• empty(): Returns true if the queue is empty, false otherwise.

• Only standard stack operations are allowed (push to top, pop from top, peek/top, size, and is empty).
• You can use multiple stacks.
• All operations must be efficient.

Thought Process

The key challenge is that a queue operates in a First-In-First-Out (FIFO) manner, while a stack operates in Last-In-First-Out (LIFO) order. If we try to use a single stack, removing the "first" element inserted is not possible without removing all elements above it.

A brute-force approach would be to, on every pop, move all elements to a temporary stack to reverse their order, pop the front, then move them back. However, this is inefficient.

The optimized approach is to use two stacks. By cleverly transferring elements between the two, we can ensure that the oldest element is always accessible for pop and peek without excessive copying.

Solution Approach

We use two stacks: in_stack and out_stack.

• Push: Always push new elements onto in_stack.
• Pop/Peek: If out_stack is empty, transfer all elements from in_stack to out_stack. This reverses the order, so the oldest element is now on top of out_stack. Then, pop or peek from out_stack.
• Empty: Queue is empty only if both stacks are empty.

• By transferring all elements from in_stack to out_stack only when needed, each element is moved at most once per operation, making the amortized cost efficient.
• This simulates the queue's FIFO behavior using two LIFO stacks.

1. To push, just add to in_stack.
2. To pop or peek, if out_stack is empty, move all items from in_stack to out_stack.
3. Then pop/peek from out_stack.

Example Walkthrough

Let's walk through the following sequence:
push(1), push(2), peek(), pop(), empty()

Step 1: push(1)

• in_stack: [1]
• out_stack: []

• in_stack: [1, 2]
• out_stack: []

• out_stack is empty, so transfer from in_stack:
• Pop 2 from in_stack, push to out_stack: [2]
• Pop 1 from in_stack, push to out_stack: [2, 1]
• Now, out_stack: [2, 1], in_stack: []
• Peek returns 1 (front of queue)

• Pop from out_stack: 1
• out_stack: [2]
• in_stack: []

• Both stacks are not empty (out_stack has 2), so returns false

Time and Space Complexity

Brute-force approach:

• Every pop requires moving all elements to a temporary stack and back: O(n) per operation.

• push: O(1) time
• pop and peek: Amortized O(1) time (each element is moved between stacks at most once per operation)
• empty: O(1) time
• Space: O(n) for storing all elements in the two stacks

Summary

By using two stacks, we efficiently simulate a queue's FIFO behavior using only LIFO stack operations. The optimized approach ensures each element is moved between stacks at most once, leading to amortized O(1) time per operation. This method elegantly bridges the conceptual gap between stacks and queues and is a classic example of using data structures in creative ways.