Implement Stack Using Queue in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Push and Pop Operations on Stack Implemented Using One Queue

What is the output of the following C++ code that implements a stack using a single queue and performs push and pop operations?

DSA C++

class Stack {
private:
    std::queue<int> q;
public:
    void push(int x) {
        int n = q.size();
        q.push(x);
        for (int i = 0; i < n; i++) {
            q.push(q.front());
            q.pop();
        }
    }
    int pop() {
        if (q.empty()) return -1;
        int val = q.front();
        q.pop();
        return val;
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    int a = s.pop();
    int b = s.pop();
    return 0;
}

A [30, 10]

B [10, 20]

C [20, 30]

D [30, 20]

💡 Hint

Remember that the push operation rotates the queue to keep the last pushed element at the front.

The push method rotates the queue so the newly pushed element is always at the front. Thus, pop returns elements in LIFO order: 30 then 20.

❓ Predict Output

intermediate

Output of Push and Pop Operations on Stack Using Two Queues

What is the output of the following C++ code that implements a stack using two queues and performs push and pop operations?

DSA C++

class Stack {
private:
    std::queue<int> q1, q2;
public:
    void push(int x) {
        q2.push(x);
        while (!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }
        std::swap(q1, q2);
    }
    int pop() {
        if (q1.empty()) return -1;
        int val = q1.front();
        q1.pop();
        return val;
    }
};

int main() {
    Stack s;
    s.push(5);
    s.push(15);
    s.push(25);
    int a = s.pop();
    int b = s.pop();
    return 0;
}

A [5, 15]

B [15, 25]

C [25, 15]

D [25, 5]

💡 Hint

The push operation moves all elements to the second queue to keep the newest element at the front.

The push method ensures the newest element is at the front of q1 by moving all elements from q1 to q2 and swapping. So pop returns 25 then 15.

🔧 Debug

advanced

Identify the Error in Stack Using One Queue Implementation

What error does the following C++ code produce when trying to pop from an empty stack implemented using one queue?

DSA C++

class Stack {
private:
    std::queue<int> q;
public:
    void push(int x) {
        q.push(x);
    }
    int pop() {
        int n = q.size();
        if (n == 0) return -1;
        for (int i = 0; i < n - 1; i++) {
            q.push(q.front());
            q.pop();
        }
        int val = q.front();
        q.pop();
        return val;
    }
};

int main() {
    Stack s;
    int a = s.pop();
    return 0;
}

A Runtime error due to popping from empty queue

B Returns -1 without error

C Throws std::out_of_range exception

D Compilation error due to missing return

💡 Hint

Check the condition before popping from the queue.

The pop method checks if the queue is empty and returns -1 safely without throwing an error.

🧠 Conceptual

advanced

Time Complexity of Push and Pop in Stack Using One Queue

What is the time complexity of push and pop operations in a stack implemented using a single queue where push rotates the queue?

A Push: O(n), Pop: O(1)

B Push: O(1), Pop: O(n)

C Push: O(n), Pop: O(n)

D Push: O(1), Pop: O(1)

💡 Hint

Consider how many elements are moved during push and pop.

Push operation rotates the queue by moving all elements, so it takes O(n). Pop just removes the front element, so O(1).

🚀 Application

expert

Final Stack State After Mixed Operations Using Two Queues

Given the following operations on a stack implemented using two queues, what is the final state of the stack (top to bottom)?

DSA C++

class Stack {
private:
    std::queue<int> q1, q2;
public:
    void push(int x) {
        q2.push(x);
        while (!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }
        std::swap(q1, q2);
    }
    int pop() {
        if (q1.empty()) return -1;
        int val = q1.front();
        q1.pop();
        return val;
    }
    std::vector<int> getStack() {
        std::vector<int> res;
        std::queue<int> temp = q1;
        while (!temp.empty()) {
            res.push_back(temp.front());
            temp.pop();
        }
        return res;
    }
};

int main() {
    Stack s;
    s.push(1);
    s.push(2);
    s.pop();
    s.push(3);
    s.push(4);
    s.pop();
    return 0;
}

A [3, 1]

B [4, 3, 1]

C [2, 1]

D [1]

💡 Hint

Track the stack after each push and pop operation carefully.

Operations: - push 1: stack = [1] - push 2: stack = [2,1] - pop: removes 2, stack = [1] - push 3: stack = [3,1] - push 4: stack = [4,3,1] - pop: removes 4, stack = [3,1] Final stack top to bottom is [3,1].

Practice

1. What is the main idea behind implementing a stack using a queue?

easy

A. Use two stacks to simulate a queue

B. Use a linked list to implement both stack and queue

C. Use one queue and reorder elements to simulate stack behavior

D. Use recursion to reverse the queue elements

Solution

1. Step 1: Understand stack and queue behavior

   A stack follows Last-In-First-Out (LIFO), while a queue follows First-In-First-Out (FIFO).

2. Step 2: Simulate stack using queue

   By reordering elements in a single queue after each push, the newest element is always at the front, simulating stack pop behavior.

3. Final Answer:

   Use one queue and reorder elements to simulate stack behavior -> Option C

4. Quick Check:

   Stack via queue = reorder elements [OK]

Hint: Rearrange queue after push to mimic stack top [OK]

Common Mistakes:

• Confusing stack with queue behavior
• Using two stacks instead of queues
• Not reordering queue after push

2. Which of the following is the correct syntax to declare a queue of integers in C++ STL?

easy

A. queue q<int>;

B. queue<int> q;

C. queue<int> q()

D. queue<int> q[];

Solution

1. Step 1: Recall C++ STL queue declaration

   The correct syntax uses template syntax: queue<int> q; declares a queue of integers.

2. Step 2: Check syntax correctness

   queue<int> q; matches the correct syntax; others have syntax errors or invalid declarations.

3. Final Answer:

   queue<int> q; -> Option B

4. Quick Check:

   Correct STL queue syntax = queue<int> q; [OK]

Hint: Use template syntax queue<int> q; for integer queue [OK]

Common Mistakes:

• Misplacing template brackets
• Using parentheses instead of semicolon
• Declaring queue as array

3. What will be the output of the following code snippet implementing stack using one queue?

class Stack {
  queue<int> q;
public:
  void push(int x) {
    q.push(x);
    int n = q.size();
    for (int i = 0; i < n - 1; i++) {
      q.push(q.front());
      q.pop();
    }
  }
  int pop() {
    int val = q.front();
    q.pop();
    return val;
  }
};

int main() {
  Stack s;
  s.push(10);
  s.push(20);
  s.push(30);
  cout << s.pop() << " ";
  s.push(40);
  cout << s.pop() << " ";
  cout << s.pop() << " ";
  return 0;
}

medium

A. 30 40 20

B. 10 20 30

C. 30 20 10

D. 20 30 40

Solution

1. Step 1: Trace push operations

   Push 10: queue = [10]
   Push 20: queue = [20, 10] after rotation
   Push 30: queue = [30, 20, 10] after rotation

2. Step 2: Trace pop and push

   Pop: returns 30, queue = [20, 10]
   Push 40: queue = [40, 20, 10]
   Pop: returns 40, queue = [20, 10]
   Pop: returns 20, queue = [10]

3. Final Answer:

   30 40 20 -> Option A

4. Quick Check:

   Stack pop order = 30, 40, 20 [OK]

Hint: After push, rotate queue to front for stack order [OK]

Common Mistakes:

• Not rotating queue after push
• Confusing queue front with stack top
• Incorrect pop order

4. Identify the error in the following stack implementation using two queues:

class Stack {
  queue<int> q1, q2;
public:
  void push(int x) {
    q1.push(x);
  }
  int pop() {
    if (q1.empty()) return -1;
    while (q1.size() > 1) {
      q2.push(q1.front());
      q1.pop();
    }
    int val = q1.front();
    q1.pop();
    swap(q1, q2);
    return val;
  }
};

medium

A. Pop operation does not handle empty stack correctly

B. Push operation should push to q2 instead of q1

C. Swap should be done before popping from q1

D. Pop operation is correct; no error

Solution

1. Step 1: Analyze pop operation logic

   Pop moves all but last element from q1 to q2, then pops last element from q1, then swaps q1 and q2.

2. Step 2: Check correctness of push and pop

   Push adds to q1; pop removes last pushed element correctly by transferring elements and swapping queues.

3. Final Answer:

   Pop operation is correct; no error -> Option D

4. Quick Check:

   Two-queue stack pop logic = correct [OK]

Hint: Pop moves elements and swaps queues to simulate stack pop [OK]

Common Mistakes:

• Swapping queues too early
• Pushing to wrong queue
• Not checking empty queue before pop

5. You want to implement a stack using a single queue but optimize the pop operation to O(1) time. Which approach is best?

hard

A. Push elements by enqueueing and dequeueing all elements except the new one

B. Use a queue and a stack together for hybrid implementation

C. Use two queues to separate push and pop operations

D. Push elements normally and rotate queue on each pop

Solution

1. Step 1: Understand time complexity trade-offs

   Push elements normally and rotate queue on each pop (push normally, rotate on pop) makes push O(1), pop O(n). Use a queue and a stack together for hybrid implementation is not pure queue. Use two queues to separate push and pop operations uses two queues, not single queue.

2. Step 2: Optimize pop to O(1) with single queue

   Enqueue new element, then dequeue and enqueue all previous elements to move new element to front. This makes pop O(1) as front is always top (matches Push elements by enqueueing and dequeueing all elements except the new one).

3. Final Answer:

   Push elements by enqueueing and dequeueing all elements except the new one -> Option A

4. Quick Check:

   Rotate queue after push for O(1) pop [OK]

Hint: Rotate queue after push to keep top at front [OK]

Common Mistakes:

• Trying to optimize pop without reordering queue
• Using two queues instead of one
• Mixing stack and queue data structures