C++ Queue Implementation using Two Stacks

"Build a queue using only two stacks" is a classic interview question. A stack gives you last in, first out; a queue needs first in, first out. The trick is that pouring one stack into another reverses the order, and reversing twice puts things back the way they were.

Problem

Implement a queue with enqueue(x) and dequeue() using two stacks and only the normal stack operations: push, pop, top and empty.

enqueue(10), enqueue(20), enqueue(30)
dequeue() → 10
dequeue() → 20
dequeue() → 30

Approach 1: make enqueue expensive

Keep the elements in stack s1 with the oldest one on top, so dequeue is just a pop. To add a new element at the bottom, move everything from s1 into s2, push the new element onto the empty s1, then move everything back. Each enqueue costs O(n), and dequeue is O(1). This is the version the earlier post showed:

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

// Queue using two stacks: enqueue is O(n), dequeue is O(1)
struct Queue {
    stack<int> s1, s2;

    void enqueue(int x) {
        while (!s1.empty()) {          // move everything to s2
            s2.push(s1.top());
            s1.pop();
        }
        s1.push(x);                    // new item goes to the bottom
        while (!s2.empty()) {          // move everything back on top of it
            s1.push(s2.top());
            s2.pop();
        }
    }

    int dequeue() {
        if (s1.empty()) return -1;
        int x = s1.top();
        s1.pop();
        return x;
    }
};

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    cout << q.dequeue() << endl;
    cout << q.dequeue() << endl;
    cout << q.dequeue() << endl;
    return 0;
}

Approach 2: lazy transfer (the one interviewers want)

There is a better way. Use one stack, in, only for pushing, and another, out, only for popping. When you need to dequeue and out is empty, pour everything from in into out. That single pour reverses the order, so the oldest element ends up on top of out.

Let us trace it. Enqueue 10, 20, 30: in holds [10, 20, 30] with 30 on top. Dequeue: out is empty, so pour; out becomes [30, 20, 10] with 10 on top, and we pop 10. Enqueue 40 goes onto in. The next two dequeues pop 20 and 30 straight from out without touching in. Only when out is empty again do we pour, and 40 comes out last, exactly as a queue should behave.

Solution in C++

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

// Queue using two stacks: enqueue is O(1), dequeue is amortised O(1)
class Queue {
    stack<int> in, out;

    void shift() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
    }

public:
    void enqueue(int x) { in.push(x); }

    int dequeue() {
        shift();
        if (out.empty()) {
            cout << "Queue is empty" << endl;
            return -1;
        }
        int x = out.top();
        out.pop();
        return x;
    }

    bool empty() { return in.empty() && out.empty(); }
};

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    cout << q.dequeue() << endl;
    q.enqueue(40);
    cout << q.dequeue() << endl;
    cout << q.dequeue() << endl;
    cout << q.dequeue() << endl;
    return 0;
}

Output

10
20
30
40

Complexity

• Approach 1: enqueue O(n), dequeue O(1).
• Approach 2: enqueue O(1). A single dequeue can cost O(n) when it triggers a pour, but each element is moved from in to out only once in its life, so the cost averaged over all operations is O(1). This is called amortised O(1).
• Both use O(n) space for n elements.

Common mistakes

• Pouring from in to out when out is not empty. That mixes old and new elements and breaks the order. Only pour when out is empty.
• Forgetting the empty-queue case. Decide what dequeue should do then (return -1, throw, or print a message) and handle it before calling top(), which is undefined on an empty std::stack.

The reverse problem is just as common: see implementing a stack using two queues. For theory practice, try the linked list, 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