Skip to content

01.ImplementStackUsingQueue.md

Latest commit

 

History

History
252 lines (170 loc) · 7.3 KB

01.ImplementStackUsingQueue.md

File metadata and controls

252 lines (170 loc) · 7.3 KB

📦 Implement Stack using Queue #225

🧩 Problem Statement

Design a data structure MyStack that simulates the behavior of a stack, but internally uses only one or more queue(s).

You must implement the following operations:

Function Description
void push(int x) Push element x onto the stack
int pop() Removes and returns the element on top of the stack
int top() Returns the element currently at the top of the stack
bool empty() Returns whether the stack is empty

Constraints:

  • Only standard queue operations are allowed (push, pop, front, size, empty).
  • You cannot use deque, list, or any stack methods.

🧠 Intuition

A stack works as: 👉 Last in, first out (LIFO) A queue works as: 👉 First in, first out (FIFO)

So we need to “reverse” the natural order of the queue when inserting elements.

💡 Key Idea

We can maintain one single queue, and every time we push a new element, we rotate the queue so that this new element comes to the front — effectively making it the top of the stack.

Example:

Step Queue State (front → back) Explanation
Push 1 [1] Only one element
Push 2 [2, 1] After pushing 2, rotate 1 to the back
Push 3 [3, 2, 1] After pushing 3, rotate 2, 1 to back

Now the front of the queue always acts as the top of the stack.

⚙️ Algorithm (using a single queue)

push(x)

  1. Store the current queue size s.

  2. Push the new element x.

  3. Rotate the queue s times:

    • Pop the front element and push it to the back.

  4. Now the new element x becomes the front (the "top" of the stack).

pop()

  • Simply pop the front element of the queue (this is the stack’s top).

top()

  • Return the front element of the queue (this is the top element).

empty()

  • Return true if the queue is empty.

✅ Clean & Commented Code

#include <queue>
using namespace std;

// Stack implemented using a single queue
class MyStack {
private:
    queue<int> q;  // internal queue
public:
    MyStack() { }

    // Push element x onto stack
    void push(int x) {
        int s = q.size();  // current size before adding
        q.push(x);         // push new element at back

        // Rotate the queue to move new element to front
        for (int i = 0; i < s; i++) {
            q.push(q.front());
            q.pop();
        }
    }

    // Removes and returns the top element
    int pop() {
        int top = q.front();  // top is at the front
        q.pop();
        return top;
    }

    // Get the top element (without removing it)
    int top() {
        return q.front();
    }

    // Returns true if stack is empty
    bool empty() {
        return q.empty();
    }
};

📈 Complexity Analysis

Operation Time Complexity Space Complexity Explanation
push() O(n) O(n) Because we rotate the queue after each push
pop() O(1) O(1) Just pops from the queue front
top() O(1) O(1) Returns front element
empty() O(1) O(1) Returns q.empty()

This approach trades push speed for pop simplicity.

🔁 Alternate Approach (for comparison)

We could also make push O(1) and pop O(n) using two queues:

Two-queue method summary:

  • push(x): simply enqueue in q1.
  • pop(): move all elements except last from q1 to q2, pop the last, then swap q1 and q2.

This reverses the trade-off:

Version Push Pop
One Queue (current) O(n) O(1)
Two Queues O(1) O(n)

🧪 Example Walkthrough

MyStack st;
st.push(10);
st.push(20);
st.push(30);

Internally after each push:

Operation Queue (front → back) Top of stack
push(10) [10] 10
push(20) [20, 10] 20
push(30) [30, 20, 10] 30

Now:

st.top();  // returns 30
st.pop();  // removes 30
st.top();  // now returns 20

🧩 Test Cases

✅ Basic Tests

MyStack st;
st.push(1);
st.push(2);
cout << st.top();   // 2
cout << st.pop();   // 2
cout << st.empty(); // false
cout << st.pop();   // 1
cout << st.empty(); // true

✅ Edge Case: Single element

MyStack st;
st.push(42);
cout << st.top();   // 42
cout << st.pop();   // 42
cout << st.empty(); // true

✅ Multiple mixed operations

MyStack st;
st.push(5);
st.push(7);
st.push(9);
st.pop();          // removes 9
st.push(11);
cout << st.top();  // 11

💡 Tips & Tricks

  • Push rotation trick: Always rotate the queue right after push so front always represents stack top.
  • Alternative optimization: If your environment allows two queues, you can choose between O(n) push or O(n) pop.
  • General idea: “Stack using queue” is a mirror-problem of “Queue using stacks” (LeetCode 225 vs 232).

🔀 Variations & Related Problems

  • 225. Implement Stack using Queues (this exact problem on LeetCode)
  • 232. Implement Queue using Stacks (the opposite)
  • Design a Deque using stacks/queues — extension of both behaviors.
  • Thread-safe stack/queue — add synchronization primitives for multithreading.

🙋 FAQs

Q: Why rotate the queue in push? A: Because new elements enter at the back by default. Rotating ensures that new elements end up at the front, representing the top of the stack.

Q: Can I use two queues instead of one? A: Yes — but you’ll need to transfer elements between them to simulate stack order. It works fine but requires more memory.

Q: Why is push O(n)? Can we make it faster? A: We can’t avoid O(n) total cost because we must invert the order at some point — either at push or pop. This version chooses to pay the cost on push, keeping pop() simple and constant time.

Q: How can I visualize the rotation? A: After adding a new element, move all existing elements behind it — this puts the new element in front, like flipping a stack upside down each time you add a plate.

🧭 Summary Table

Method Data Structures Push Pop Top Extra Space Simplicity
Single Queue (current) 1 queue O(n) O(1) O(1) O(n) ✅ Simple
Two Queues 2 queues O(1) O(n) O(n) O(2n) Slightly longer code