C++ program to implement Stack using Two Queues

This is the mirror image of building a queue from two stacks. Here we want last in, first out behaviour, but all we have are queues, which only let us add at the back and remove from the front. The solution is to keep the queue arranged so that the most recent element is always at the front.

Problem

Implement a stack with push(x), pop() and top() using two queues. If the stack is empty, pop() should return -1.

push 10, 20, 30, 40, 50
pop() seven times → 50 40 30 20 10 -1 -1

Approach: make push do the work

We keep queue q1 in stack order, with the top of the stack at the front. To push x:

1. Put x into the empty queue q2.
2. Move every element from q1 into q2, one by one. They line up behind x in the same order they were in.
3. Swap the two queues. Now q1 has x at the front, followed by the older elements, and q2 is empty again.

After that, pop and top are just "look at the front of q1".

A short trace: push 10 gives q1 = [10]. Push 20: q2 = [20], then move 10 across, q2 = [20, 10], swap, so q1 = [20, 10]. Push 30: q2 = [30, 20, 10] after the moves, and after the swap q1 = [30, 20, 10]. Pop returns 30, which is correct for a stack.

Solution in C++

#include <iostream>
#include <queue>
using namespace std;

// Stack using two queues: push is O(n), pop and top are O(1)
class Stack {
    queue<int> q1, q2;   // q1 always holds the elements in stack order (top at the front)

public:
    void push(int x) {
        q2.push(x);                  // new element goes first in q2
        while (!q1.empty()) {        // then everything already in the stack follows it
            q2.push(q1.front());
            q1.pop();
        }
        swap(q1, q2);                // q1 is now in the right order again
    }

    int pop() {
        if (q1.empty()) return -1;   // -1 means the stack is empty
        int x = q1.front();
        q1.pop();
        return x;
    }

    int top() { return q1.empty() ? -1 : q1.front(); }
    int size() { return q1.size(); }
};

int main() {
    Stack s;
    for (int x : {10, 20, 30, 40, 50}) s.push(x);
    for (int i = 0; i < 7; i++) cout << s.pop() << endl;
    return 0;
}

Output

50
40
30
20
10
-1
-1

The last two pops return -1 because the stack is already empty after five pops.

Complexity

• push: O(n), because every existing element is moved once.
• pop and top: O(1).
• Space: O(n).

The other way round

You can also make push cheap and pop expensive: push simply adds to q1, and pop moves all but the last element into q2, removes the last one, and swaps the queues. Pick the version that makes the more frequent operation fast. In an interview, mention both and explain the trade-off.

A neat follow-up: you can do this with a single queue. After adding x at the back, rotate the queue by taking the front element and adding it to the back size − 1 times, which brings x to the front.

See also a queue using two stacks, and the stack and queue MCQs.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More C and CPP solutions All coding problems MCQ practice