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:

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

Notes:

• You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, 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 operations of a stack.

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 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 the 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 false.

Explanation:

The key idea is to use stack2 to efficiently retrieve the front element of the queue. Pushing is straightforward. Popping and peeking require transferring elements from stack1 to stack2 to reverse the order, ensuring FIFO behavior. This transfer only happens once per sequence of pops or peeks.

Code:

#include <stack>

class MyQueue {
public:
    stack<int> stack1;
    stack<int> stack2;

    MyQueue() {
        
    }
    
    void push(int x) {
        stack1.push(x);
    }
    
    int pop() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        int top = stack2.top();
        stack2.pop();
        return top;
    }
    
    int peek() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        return stack2.top();
    }
    
    bool empty() {
        return stack1.empty() && stack2.empty();
    }
};

Complexity:

• Time Complexity:

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

• Space Complexity: O(n), where n is the number of elements in the queue. This is due to the use of two stacks to store the elements.