232. Implement Queue using Stacks

Hello, reader 👋🏽 ! Welcome to day 76 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 232. Implement Queue using Stacks.

🤔 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 as follows:

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

• E.g.:

  ["MyQueue", "push", "push", "peek", "pop", "empty"] 
  [[], [1], [2], [], [], []]
  
  => [null, null, null, 1, 1, false]
  

💬 Thought Process - Using Two Stacks

• Queue is a data structure with two sides:

  • rear -> elements are inserted from this side

  • front -> elements are removed from this side

• With queue, the element entered first is removed first. Hence FIFO or first in first out.

• Whereas stack is a data structure where insertion and removal happens from only one side: top.

• It is a data structure where the element pushed last is accessed/ removed first.

• Hence to ensure that we always access the first element added, we can maintain two stacks.

• We add elements to one of the stacks, let's call this elements.

• The other stack, let's call this helper will be used to push elements from elements stack to it.

• Let's now focus on the three operations that are supported by a queue:

  • push(x)

    • This operation will be straightforward. We will push x into the elements stack.

    • The image below depicts the push() operations for three elements.

      

  • pop()

    • We will make use of helper stack to get the first pushed element.

    • When the helper stack is empty, we will push all the elements from elements stack to helper stack.

      • This operation will ensure that the first element that was added to elements stack be on top of helper stack.

    • Then we will pop the top most element from helper stack and return it.

    • If the helper stack is not empty, then we will simply return the top most element, which would be the least recently added element.

      

  • peek()

    • This will also use the helper stack in a similar manner as pop().

    • If helper stack is not empty, then return the top most element.

    • Else, push all elements from elements stack to helper and then return top most from helper stack.

    ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1671212057333/p9SzXx8Iz.png align="center")

*   `empty()`

    *   This operation is used to check if the queue is empty.

    *   We we return true if both the `elements` and `helper` stack are empty, else false.

👩🏽‍💻 Solution - Using Two Stacks

• Below is the code for the approach for solving this problem using two stacks.

class MyQueue {
    Stack<Integer> elements, helper;
    public MyQueue() {
        elements = new Stack();
        helper = new Stack();
    }

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

    public int pop() {
        if(!helper.isEmpty()) return helper.pop();

        while(!elements.isEmpty()) {
            helper.push(elements.pop());
        }

        return helper.pop();
    }

    public int peek() {
        if(!helper.isEmpty()) return helper.peek();

        while(!elements.isEmpty()) {
            helper.push(elements.pop());
        }

        return helper.peek();
    }

    public boolean empty() {
        return helper.isEmpty() && elements.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

Time Complexity:
    - push: O(1)
    - pop: O(1)* 

* amortized

• You can find the link to the GitHub repo for this question here: 232. Implement Queue using Stacks.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!