algoadvance

Leetcode 232. Implement Queue using Stacks

Problem Statement

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).

Implementation Requirements:

• 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 whether the queue is empty.

Constraints:

• You must use only standard stack operations — which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack using a deque or list if needed.

Clarifying Questions

1. Should I assume the elements are non-negative integers, or can they also be negative?
   • Elements can be any integer.
2. Is there a maximum number of elements that the queue should support?
   • No specific limit, handle as many elements as possible within the constraints of typical memory limits.
3. Can we assume that pop and peek will not be called on an empty queue?
   • No, handle such cases gracefully, either by throwing an error or returning a specific value.

Strategy

To implement this queue using two stacks, we can use the following strategy:

• Use two stacks, input and output.
• For the push operation, simply push the element onto the input stack.
• For the pop operation, if the output stack is empty, pour all the elements from the input stack into the output stack, then pop the top of the output stack.
• For the peek operation, if the output stack is empty, pour all the elements from the input stack into the output stack, then peek the top element of the output stack.
• The empty operation should check if both stacks are empty.

This way, we ensure that the oldest elements are popped and peeked first, maintaining the queue order.

Code

Here is the C++ implementation of the MyQueue class:

#include <stack>

class MyQueue {
private:
    std::stack<int> input;
    std::stack<int> output;

public:
    MyQueue() {
    }
    
    void push(int x) {
        input.push(x);
    }
    
    int pop() {
        if (output.empty()) {
            while (!input.empty()) {
                output.push(input.top());
                input.pop();
            }
        }
        int val = output.top();
        output.pop();
        return val;
    }
    
    int peek() {
        if (output.empty()) {
            while (!input.empty()) {
                output.push(input.top());
                input.pop();
            }
        }
        return output.top();
    }
    
    bool empty() {
        return input.empty() && output.empty();
    }
};

Time Complexity

• Push Operation (push): O(1) - Pushing onto a stack is an O(1) operation.
• Pop Operation (pop): Amortized O(1) - Each element is moved from input to output at most once.
• Peek Operation (peek): Amortized O(1) - Each element is moved from input to output at most once.
• Check Empty Operation (empty): O(1) - Simply checking if both stacks are empty.

Therefore, while individual pop and peek operations may sometimes take linear time in the worst case when elements are moved between the stacks, on average, each operation runs in constant time.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?