Implement Queue using Stacks easy

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

Implement the MyQueue class:

• MyQueue() Initializes the MyQueue object.
• 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.

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] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

Example 2:

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

Steps:

1. Initialization: We'll use two stacks, stack1 and stack2. stack1 will be the primary stack for pushing elements. stack2 will be used as a temporary stack to help with pop and peek operations.

2. push(x): Simply push the element x onto stack1.

3. pop():

   • If stack2 is empty, transfer all elements from stack1 to stack2 (reversing their order).
   • Pop and return the top element from stack2.

4. peek():

   • If stack2 is empty, transfer all elements from stack1 to stack2.
   • Return the top element of stack2.

5. empty(): Return True if both stack1 and stack2 are empty; otherwise, return False.

Explanation:

The key idea is to use stack2 to efficiently retrieve the front element of the queue. Since stacks operate in LIFO (Last-In, First-Out) order, we shift elements from stack1 to stack2 to reverse the order, effectively making the original front element the top of stack2. This allows us to retrieve the front element in O(1) time after the initial transfer (which is amortized O(1) over many operations).

Code:

class MyQueue:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

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

    def pop(self) -> int:
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

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

    def empty(self) -> bool:
        return not self.stack1 and not self.stack2

Complexity:

• Time complexity:
  • push(x): O(1)
  • pop(): Amortized O(1). In the worst case, all elements from stack1 are transferred to stack2, but this only happens once for each element in the queue.
  • peek(): Amortized O(1). Similar reasoning to pop().
  • empty(): O(1)
• Space complexity: O(N), where N is the number of elements in the queue. We use two stacks to store the elements.