How to implement queue with a single stack in C++

Question

In this C++ code I'm implementing Queue with a Single stack instance. I found this code in GeeksForGeeks. Url Here

#include <bits/stdc++.h>
using namespace std;
class Queue
{
private:
    stack<int> s;

public:
    void enque(int x)
    {
        s.push(x);
    }
    int deque()
    {
        if (s.empty())
        {
            cout << "Q is empty" << endl;
            return -1;
        }
        int x = s.top();
        s.pop();
        if (s.empty())
        {
            return x;
        }
        // I'm not able to understand these 3 lines after this comment
        int item = deque();
        s.push(x);
        return item;
    }
};
int main()
{
    Queue q;
    q.enque(1);
    q.enque(2);
    q.enque(3);
    cout << "Output: " << q.deque() << endl;
    cout << "Output: " << q.deque() << endl;
    cout << "Output: " << q.deque() << endl;
    cout << "Output: " << q.deque() << endl;
    return 0;
}

But I cannot understand these 3 lines

int item = deque();
s.push(x);
return item;

Problem

How after calling deque() recursively the compiler reaches the next lines to push x again to the stack. And how it is retaining the value of x after recursive function call.

Forget that gfg garbage collection unless you want to learn how to write really bad C++ code. [Why should I not `#include `?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Evg, Jun 27 '21 at 06:17
Run the code in a *debugger* and witness the modifications of the variables and their content in action. It would also help if you considered what handcuffs you're wearing when implementing a queue with arguably the worst possible back-end container (a stack) one could choose to do it with. A pencil, paper and a few manual iterations of the only possible algorithm would be pretty telling. — WhozCraig, Jun 27 '21 at 06:17
Every recursive call of `deque` uses a different location in memory to store the values of local variables. This memory is used to store the value of `x`. — fabian, Jun 27 '21 at 06:31
You should be careful about stuff on geeksforgeeks. Mostly try to avoid it as much as possible. In many cases it teaches very very bad programming practices. C++ stl provides a lot more efficient usage.. std::queue will probably serve your purpose in much better way. In your example you are basically recursively emptying stack and returning back thing at bottom. — chandola, Jun 27 '21 at 06:38
The code might be easier to understand if you consider you aren't really using a single stack you are also using the built-in stack to temporarily store the values. Safe to say this is a terribly inefficient way to implement a queue, use a proper queue data structure — Alan Birtles, Jun 27 '21 at 06:40
I'm learning DSA so I tried to implement queue with stack and came upon this. Thanks — Soumalya Bhattacharya, Jun 27 '21 at 06:53

score 2 · Accepted Answer · answered Jun 27 '21 at 07:05

The code isn't really using a single stack, its using the built-in stack as a second stack via the recursive call to deque. The code is equivalent to:

#include <iostream>
#include <stack>

class Queue
{
private:
    std::stack<int> s;

public:
    void enque(int x)
    {
        s.push(x);
    }
    int deque()
    {
        if (s.empty())
        {
            std::cout << "Q is empty\n";
            return -1;
        }
        std::stack<int> temp;
        while (s.size() != 1)
        {
            temp.push(s.top());
            s.pop();
        }
        int result = s.top();
        s.pop();
        while (!temp.empty())
        {
            s.push(temp.top());
            temp.pop();
        }
        return result;
    }
};
int main()
{
    Queue q;
    q.enque(1);
    q.enque(2);
    q.enque(3);
    std::cout << "Output: " << q.deque() << "\n";
    std::cout << "Output: " << q.deque() << "\n";
    std::cout << "Output: " << q.deque() << "\n";
    std::cout << "Output: " << q.deque() << "\n";
    return 0;
}

I can't think of a reason you'd implement a queue this way, as the queue grows in size deque gets more and more expensive, using the original code you'd ultimately end up with a stack overflow. If you need a queue use std::queue or std::deque (by default std::queue is just a wrapper round std::deque which hides the push_front/pop_back methods)

How to implement queue with a single stack in C++

1 Answers1