DAY 86 - 225. Implement Stack using Queues

Hey Guys! Nayan here and we are going to solve another daily leetcode question. I will be taking you guys from intuition to algorithm so stick with me. Incase you don't understand some part , please feel free to ask in comments.

Question: 225. Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.

Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Example 1:

Input:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output:
[null, null, null, 2, 2, false]
Explanation:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Pre-Requisites:

Breaking down the question:

• So we need to construct a stack using queue or queues. Let's understand what a stack is if you don't know.
• A stack is a FILO(First in, Last out) operational data structure. As the name suggests it's a stack like thing.

• A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. In simpler terms, the last element added to the stack is the first one to be removed. It can be visualized as a stack of items, similar to a stack of plates.

• A stack DS has few operations that we need to implement using queue.

• We need to know what we can do with a queue first.

• Imagine a queue like a line of people waiting at a ticket counter. The first person who arrives is the first one to get the ticket and leave the line. New people join the line at the end, and they wait their turn. This concept is similar to how a queue data structure works in programming.

• Read more about queue at GFG QUEUE

Two-Queue Approach:

To solve this problem, I've employed a solution that utilizes two queues: q1 and q2. The main idea is to mimic the behavior of a stack by transferring elements between these two queues.

Initialization: I start by initializing two empty queues, q1 and q2, which will serve as the building blocks for simulating the stack behavior.

Push Operation: Pushing an element onto the stack is a simple process. I achieve this by adding the element to the back of q1.

Pop Operation: To simulate the pop operation, I transfer all elements from q1 except the last one to q2. The last element remaining in q1 is the element to be popped, and I remove it. After that, I swap the roles of q1 and q2 using the std::swap function. This prepares q2 for the next pop operation.

Top Operation: Similar to the pop operation, the top operation involves transferring all elements except the last one from q1 to q2. I temporarily store the last element in q1 as the top element. Then, I move this element from q1 to q2, and I swap the roles of the two queues back to their original positions.

Empty Operation: Checking if the stack is empty is a straightforward operation. I simply check if q1 is empty and return the result.

class MyStack {
private:
    std::queue<int> q1;
    std::queue<int> q2;

public:
    MyStack() {}

    void push(int x) {
        q1.push(x);
    }

    int pop() {
        while (q1.size() > 1) {
            q2.push(q1.front());
            q1.pop();
        }

        int popped_element = q1.front();
        q1.pop();

        std::swap(q1, q2);

        return popped_element;
    }

    int top() {
        while (q1.size() > 1) {
            q2.push(q1.front());
            q1.pop();
        }

        int top_element = q1.front();
        q2.push(q1.front());
        q1.pop();

        std::swap(q1, q2);

        return top_element;
    }

    bool empty() {
        return q1.empty();
    }
};

Complexity Analysis: