232. Implement Queue using Stacks

Problem Description

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

• You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2]
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, peek, and empty
• All the calls to pop and peek are valid

Follow-up:

Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

Python Solution

class MyQueue:
    def __init__(self):
        # Stack for pushing elements
        self.stack1 = []
        # Stack for popping elements
        self.stack2 = []

    def push(self, x: int) -> None:
        # Always push to stack1
        self.stack1.append(x)

    def pop(self) -> int:
        # If stack2 is empty, transfer all elements from stack1
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

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

    def empty(self) -> bool:
        # Queue is empty if both stacks are empty
        return not self.stack1 and not self.stack2

Java Solution

class MyQueue {
    private Stack stack1;
    private Stack stack2;

    public MyQueue() {
        // Stack for pushing elements
        stack1 = new Stack<>();
        // Stack for popping elements
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
        // Always push to stack1
        stack1.push(x);
    }
    
    public int pop() {
        // If stack2 is empty, transfer all elements from stack1
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    
    public int peek() {
        // If stack2 is empty, transfer all elements from stack1
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    
    public boolean empty() {
        // Queue is empty if both stacks are empty
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

C++ Solution

class MyQueue {
private:
    stack stack1;  // Stack for pushing elements
    stack stack2;  // Stack for popping elements

public:
    MyQueue() {
        
    }
    
    void push(int x) {
        // Always push to stack1
        stack1.push(x);
    }
    
    int pop() {
        // If stack2 is empty, transfer all elements from stack1
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int result = stack2.top();
        stack2.pop();
        return result;
    }
    
    int peek() {
        // If stack2 is empty, transfer all elements from stack1
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        return stack2.top();
    }
    
    bool empty() {
        // Queue is empty if both stacks are empty
        return stack1.empty() && stack2.empty();
    }
};

JavaScript Solution

var MyQueue = function() {
    // Stack for pushing elements
    this.stack1 = [];
    // Stack for popping elements
    this.stack2 = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    // Always push to stack1
    this.stack1.push(x);
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    // If stack2 is empty, transfer all elements from stack1
    if (this.stack2.length === 0) {
        while (this.stack1.length > 0) {
            this.stack2.push(this.stack1.pop());
        }
    }
    return this.stack2.pop();
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    // If stack2 is empty, transfer all elements from stack1
    if (this.stack2.length === 0) {
        while (this.stack1.length > 0) {
            this.stack2.push(this.stack1.pop());
        }
    }
    return this.stack2[this.stack2.length - 1];
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    // Queue is empty if both stacks are empty
    return this.stack1.length === 0 && this.stack2.length === 0;
};

C# Solution

public class MyQueue {
    private Stack stack1;  // Stack for pushing elements
    private Stack stack2;  // Stack for popping elements

    public MyQueue() {
        stack1 = new Stack();
        stack2 = new Stack();
    }
    
    public void Push(int x) {
        // Always push to stack1
        stack1.Push(x);
    }
    
    public int Pop() {
        // If stack2 is empty, transfer all elements from stack1
        if (stack2.Count == 0) {
            while (stack1.Count > 0) {
                stack2.Push(stack1.Pop());
            }
        }
        return stack2.Pop();
    }
    
    public int Peek() {
        // If stack2 is empty, transfer all elements from stack1
        if (stack2.Count == 0) {
            while (stack1.Count > 0) {
                stack2.Push(stack1.Pop());
            }
        }
        return stack2.Peek();
    }
    
    public bool Empty() {
        // Queue is empty if both stacks are empty
        return stack1.Count == 0 && stack2.Count == 0;
    }
}