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, pop, peek, 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 without removing it.
• 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]
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]

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

Steps

The core idea is to use one stack (stack1) for pushing elements and another stack (stack2) for popping elements. When push is called, we simply push onto stack1. When pop or peek is called, if stack2 is empty, we transfer all elements from stack1 to stack2 (reversing their order). Then we can perform the pop or peek operation from stack2.

Explanation

1. push(x): We directly push the element x onto stack1.

2. pop():

   • If stack2 is empty, we move all elements from stack1 to stack2. This reverses the order, making the element that was pushed first now at the top of stack2.
   • Then we pop and return the top element from stack2.

3. peek():

   • Similar to pop(), if stack2 is empty, we move elements from stack1 to stack2.
   • Then we return the top element of stack2 without popping it.

4. empty(): We check if both stack1 and stack2 are empty.

Code

class MyQueue {
    stack1: number[];
    stack2: number[];

    constructor() {
        this.stack1 = [];
        this.stack2 = [];
    }

    push(x: number): void {
        this.stack1.push(x);
    }

    pop(): number {
        if (this.stack2.length === 0) {
            while (this.stack1.length > 0) {
                this.stack2.push(this.stack1.pop()!);
            }
        }
        return this.stack2.pop()!;
    }

    peek(): number {
        if (this.stack2.length === 0) {
            while (this.stack1.length > 0) {
                this.stack2.push(this.stack1.pop()!);
            }
        }
        return this.stack2[this.stack2.length - 1];
    }

    empty(): boolean {
        return this.stack1.length === 0 && this.stack2.length === 0;
    }
}

Complexity

• Time Complexity:

  • push(x): O(1)
  • pop(): O(n) in the worst case (when stack2 is empty and all elements from stack1 need to be transferred). Amortized time complexity is O(1).
  • peek(): O(n) in the worst case (similar to pop()). Amortized time complexity is O(1).
  • empty(): O(1)

• Space Complexity: O(n), where n is the number of elements in the queue. We use two stacks, and in the worst case, both stacks can contain all the elements.