How to reverse a Deque using stack?

Question

Here is my code:-

stack <int> intStack;

    while (!adaqueue.empty())
    {
        intStack.push(adaqueue.front());
        adaqueue.pop_front();
    }
    while (!intStack.empty())
    {
        adaqueue.push_front(intStack.top());
        intStack.pop();
    }

It isn't giving the right output. Say, for example, 12 and 45 are the items in the deque respectively. If I use the code above for reversing the deque it's giving wrong output. If I try to print the front item it's giving me 12 instead of 45. What could be the potential error of my code? N.B. The code in c++ language.

Answer 1

What you want to do here is that in the second while loop you want to remove the top from the stack and then add it at the back of the queue. This way you will reverse the order. Try sketching it out on paper. It will help to visualize it.

Initial state of queue (1 is the front):

{1,2,3,4,5}

After adding it to the stack (5 is the top):

{5,4,3,2,1}

And then after taking from the top of the stack and adding to the back of the queue, we retain the same order(5):

S {5,4,3,2,1}
Q {}

S {4,3,2,1}
Q {5}

S {3,2,1}
Q {5,4}

S {2,1}
Q {5,4,3}

and so on. In the end we have reversed the queue:

S {}
Q {5,4,3,2,1}