Implement Queue using Stacks easy

Problem Statement

Implement a queue using two stacks. You should implement the MyQueue class which supports the following methods:

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

Notes:

• You must use only standard operations of a stack: push to top, peek/top, pop and empty.
• You must use only 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]

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

Steps

The key idea is to use one stack (stack1) for pushing elements and another stack (stack2) for popping elements. When pop() or peek() is called, and stack2 is empty, we transfer all elements from stack1 to stack2. This reverses the order, making the element that was initially pushed first now at the top of stack2.

1. push(x): Push the element x onto stack1.

2. pop():

   • If stack2 is empty, transfer all elements from stack1 to stack2.
   • Pop and return the top element from stack2.

3. peek():

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

4. empty(): Return true if both stack1 and stack2 are empty, otherwise return false.

Explanation

The algorithm ensures that the FIFO (First-In, First-Out) property of a queue is maintained even though we are using stacks (which are LIFO - Last-In, First-Out). By transferring elements between the stacks strategically, we effectively reverse the order when needed for popping and peeking.

Code

import java.util.Stack;

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

Complexity

• Time Complexity:

  • push(x): O(1)
  • pop(): O(n) in the worst case (when stack2 is empty and all elements need to be transferred). Amortized O(1).
  • peek(): O(n) in the worst case (when stack2 is empty and all elements need to be transferred). Amortized 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. Amortized space complexity remains O(n). The space usage is proportional to the number of elements stored.