How to Reverse a Queue in C++

Reverse a Queue

 

Queue is a popular First in First out linear user defined data structure, and as a linear data structure, it is possible to reverse a queue. There more than one method to reverse an entire queue. Here in the article we will see how to reverse a queue using a Stack and a recursive function calling.


How to Reverse a Queue | PrepInsta
Reverse a Queue

Method 1: Reverse a Queue using Stack

The stack is a last in First out Data structure, it is easy to reverse any linear data structure using stack.

  • First we will pop elements from the queue one by one, and push them into the stack.
  • When the stack is empty, we will stop that ans start popping out elements one by one from the stack and push it into the queue.
  • Stack is last in first out, so the elements sent the last will be reentering into the queue first.
  • And the Element which was pushed at the first time, will re enter into the queue at last.
  • The order will be changed and reversed.

Note: The queue must be called by reference.

Reverse a queue using stack
Reverse a Queue using Recursion

Method 2: Reverse a Queue using Recursion

People who are familiar with recursion, knows recursion works just like stack, mainly because recursion is done using the stack memory of the RAM.

  • The Base condition of the function will be to return if the queue is empty. If the queue is empty it will not call the recursive function and return.
  • Otherwise. It will pop out one element and the popped value will be stored. 
  • Then we will call the recursive function.
  • Then we push the popped value when the recursion is returing back.
  • The values popped the first will come back at the last function return.

Note: The queue must be called by reference.

The code to implement this:

#include<bits/stdc++.h>
using namespace std;

void Reverse_Queue_using_Stack(queue<int&q)
{
  stack<ints;
  while(!q.empty())
  {s.push(q.front());q.pop();}
  while(!s.empty())
  {q.push(s.top());s.pop();}
}

void Reverse_Queue_using_Recrustion(queue<int&q)
{
  int a=q.front();
  if(q.size()==1return;
  q.pop();
  Reverse_Queue_using_Recrustion(q);
  q.push(a);
}

void Show(queue<intq)
{
  int a=q.front();q.pop();
  cout<<a<<” “;
  if(q.empty()) {q.push(a);return;}
  Show(q);
  q.push(a);
}

int main()
{
  queue<intq;
  q.push(1);q.push(2);q.push(3);
  q.push(4);q.push(5);q.push(6);
  cout<<“At first the queue is: “;
  Show(q);cout<<endl;
  Reverse_Queue_using_Stack(q);
  cout<<“After reversing the queue using stack, now to queue: “;
  Show(q);cout<<endl;
  Reverse_Queue_using_Recrustion(q);
  cout<<“After again reversing the queue using recursion, now to queue: “;
  Show(q);
}

Output:

At first the queue is: 1 2 3 4 5 6
After reversing the queue using stack, now to queue: 6 5 4 3 2 1
After again reversing the queue using recursion, now to queue: 1 2 3 4 5 6

Article is contributed by Rahit Saha