algoadvance

Leetcode 225. Implement Stack using Queues

Problem Statement

Leetcode problem 225 requires us to implement a Stack using Queues. The goal is to implement the following operations for the stack:

• void push(int x): Push element x onto stack.
• int pop(): Removes the element on top of the stack and returns it.
• int top(): Get the top element.
• bool empty(): Returns whether the stack is empty.

Clarifying Questions

1. Queue Type: Can we use both single-ended queues (like std::queue) or double-ended queues (std::deque), or is it restricted to a specific type?
   • We’ll assume standard single-ended queues (std::queue) are to be used.
2. Efficiency Concerns: Is there a preference for more efficient operations for push or pop or should we try to balance the efficiency of both?
   • We’ll assume that there’s no specific preference and that both operations should be reasonably efficient.

Code

Here’s the implementation of the Stack using Queues:

#include <queue>

class MyStack {
private:
    std::queue<int> q1; // Main queue to hold stack elements

public:
    MyStack() {
    }
    // Push element x onto stack.
    void push(int x) {
        int size = q1.size();
        q1.push(x);

        // Move all elements before x to the back of the queue to maintain stack order
        for(int i = 0; i < size; i++) {
            q1.push(q1.front());
            q1.pop();
        }
    }
    
    // Removes the element on top of the stack and returns it.
    int pop() {
        int topElement = q1.front();
        q1.pop();
        return topElement;
    }
    
    // Get the top element.
    int top() {
        return q1.front();
    }
    
    // Returns whether the stack is empty.
    bool empty() {
        return q1.empty();
    }
};

Strategy

1. Using a Single Queue: We use a single queue q1 to simulate stack operations.

   • Push Operation:
     • When we push an element x, we first get the size of the queue.
     • We then enqueue the new element x.
     • We move all the other elements that were in the queue prior to x to the back of the queue. This ensures that element x is always at the front, simulating stack behavior.
   • Pop Operation:
     • Simply dequeue the front element since it represents the top of the stack.
   • Top Operation:
     • Directly return the front element of the queue without removing it.
   • Empty Operation:
     • Check if the queue is empty.

Time Complexity

• Push Operation: O(n), where n is the number of elements in the queue before the push operation. This is because we need to reorder the elements in the queue after inserting a new one.
• Pop Operation: O(1), as we are directly dequeuing the front element.
• Top Operation: O(1), as we are directly accessing the front element.
• Empty Operation: O(1), as we are simply checking if the queue is empty.

By leveraging a single queue and adjusting its order during insertions, we maintain the stack’s LIFO (Last In, First Out) property efficiently for typical stack operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?