Implement Queue using Stacks easy

Problem Statement

Implement a queue using two stacks. The queue should support the following operations:

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

You must use only standard operations of a stack: push to top, peek/top, pop from top, size, and empty.

Note: You must solve the problem using two stacks.

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. Data Structures: 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 facilitate pop and peek operations.

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

3. pop():

   • If stack2 is empty, we transfer all elements from stack1 to stack2 (reversing their order). This makes the element that was initially at the bottom of stack1 (the front of the queue) now at the top of stack2.
   • Then, we pop and return the top element from stack2.

4. peek():

   • Similar to pop(), if stack2 is empty, transfer elements from stack1 to stack2.
   • Then, return the top element of stack2.

5. empty(): Check if both stack1 and stack2 are empty.

Explanation:

The key idea is that a queue's FIFO (First-In, First-Out) behavior is reversed when using stacks (LIFO - Last-In, First-Out). By transferring elements between the two stacks, we effectively reverse the order, allowing us to simulate a queue.

Code:

using System.Collections.Generic;

public class MyQueue {
    private Stack<int> stack1;
    private Stack<int> stack2;

    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<int>();
        stack2 = new Stack<int>();
    }

    /** Push element x to the back of queue. */
    public void Push(int x) {
        stack1.Push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int Pop() {
        if (stack2.Count == 0) {
            while (stack1.Count > 0) {
                stack2.Push(stack1.Pop());
            }
        }
        return stack2.Pop();
    }

    /** Get the front element. */
    public int Peek() {
        if (stack2.Count == 0) {
            while (stack1.Count > 0) {
                stack2.Push(stack1.Pop());
            }
        }
        return stack2.Peek();
    }

    /** Returns whether the queue is empty. */
    public bool Empty() {
        return stack1.Count == 0 && stack2.Count == 0;
    }
}

Complexity:

• Time Complexity:
  • push(x): O(1)
  • pop(): O(n) in the worst case (when all elements from stack1 need to be transferred to stack2) , O(1) on average.
  • peek(): O(n) in the worst case, O(1) on average.
  • 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.