algoadvance

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, pop, peek, 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 whether the queue is empty.

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 standard stack operations.

---

Clarifying Questions

1. Is the input size constrained?
   • Not necessarily. The main concern is ensuring the operations adhere strictly to the stack operations.
2. Can we assume the inputs are valid?
   • Yes, assume that inputs given to each method are valid and within expected ranges.
3. Should the solution be optimized for any specific operation?
   • The operations are evenly distributed; thus, our implementation should aim for overall efficiency in both push and pop operations.

---

Strategy

We’ll use two stacks to simulate the queue:

1. Stack1 (in_stack): Used for enqueue operations.
2. Stack2 (out_stack): Used for dequeue operations.

Operations:

• Push:
  • Directly push elements onto in_stack.
• Pop and Peek:
  • If out_stack is empty, pop all elements from in_stack and push them onto out_stack (this reverses the order, simulating FIFO).
  • Pop/Peek elements from out_stack.
• Empty:
  • Return True if both in_stack and out_stack are empty.

This approach ensures that we always get the front element in O(1) average time, while pushes are O(1) and pops are amortized O(1) due to potential transfer between stacks.

---

Code

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._transfer()
        return self.out_stack.pop()

    def peek(self) -> int:
        self._transfer()
        return self.out_stack[-1]

    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack
    
    def _transfer(self) -> None:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

---

Time Complexity

• Push: O(1) — Each push operation directly puts the element onto the in_stack.
• Pop: Amortized O(1) — While out_stack is empty, elements are transferred from in_stack in O(n) time, but each individual element is popped only once.
• Peek: Amortized O(1) — Similar to pop, but no elements are removed.
• Empty: O(1) — Just checks if both stacks are empty.

This implementation efficiently simulates a queue using two stacks, ensuring all operations adhere to the required time complexities.

Try our interview co-pilot at AlgoAdvance.com

• 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?