How to Reverse a Queue in C++

November 2, 2023

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.

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.

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.

Types of Queues in Data Structure

Application of Queue Data Structure

Insertion in Queues Program (Enqueuing)

Queues using Linked Lists

Implement Queue using Stack

The code to implement this:

Method 1

Method 2

Method 1

Run

 &q)
{
  stack s;
  while (!q.empty ())
    {
      s.push (q.front ());
      q.pop ();
    }
  while (!s.empty ())
    {
      q.push (s.top ());
      s.pop ();
    }
    return;
}
void Show (queue< int> &q)
{
  queue p=q;
  while(!p.empty())
  {
      int a = p.front();
      p.pop();
      cout << a << " ";
  }
}
int main ()
{
  queue< int> q ;
  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);
}

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

Method 2

Run

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

void Reverse_Queue_using_Recursion (queue<long long int> &q)
{
  int a = q.front ();
  if (q.size () == 1)
    return;
  q.pop ();
  Reverse_Queue_using_Recursion (q);
  q.push (a);
  return;
}
void Show (queue<long long int> &q)
{
  queue<long long int> p=q;
  while(!p.empty())
  {
      int a = p.front();
      p.pop();
      cout << a << " ";
  }
}
int main ()
{
  queue<long long int> q ;
  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_Recursion (q); 
  cout << "After 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 recursion, now to queue: 6 5 4 3 2 1

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Stacks

Introduction to Stack in Data Structure
Click Here
Operations on a Stack
Click Here
Stack: Infix, Prefix and Postfix conversions
Click Here
Stack Representation in –
C | C++ | Java
Representation of a Stack as an Array. –
C | C++ | Java
Representation of a Stack as a Linked List. –
C | C++ | Java
Infix to Postfix Conversion –
C | C++ | Java
Infix to prefix conversion in –
C | C++ | Java
Postfix to Prefix Conversion in –
C | C++ | Java

Queues

Queues in Data Structures (Introduction)
Click Here
Queues Program in C and implementation
Click Here
Implementation of Queues using Arrays | C Program
Click Here
Types of Queues in Data Structure
Click Here
Application of Queue Data Structure
Click Here
Insertion in Queues Program (Enqueuing) –
C | C++ | Java
Deletion (Removal) in Queues Program(Dequeuing) –
C | C++ | Java
Reverse a Queue –
C | C++ | Java
Queues using Linked Lists –
C | C++ | Java
Implement Queue using Stack –
C | C++ | Java
Implement Queue using two Stacks –
C | C++ | Java

Circular Queues

Circular queue in Data Structure
Click Here
Applications of Circular Queues
Click Here
Circular queue in –
C | C++ | Java
Circular queue using Array –
C | C++ | Java
Circular Queue using Linked Lists –
C | C++ | Java

Priority Queue

Application of Priority Queue
Priority Queue Example
Priority Queue Introduction –
C | C++ | Java
Priority Queue Implementation using Array –
C | C++ | Java
Priority Queue using Linked List –
C | C++ | Java
Priority Queue Insertion and Deletion-
C | C++ | Java

Stacks

Introduction to Stack in Data Structure
Operations on a Stack
Stack: Infix, Prefix and Postfix conversions
Stack Representation in – C | C++ | Java
Representation of a Stack as an Array. – C | C++ | Java
Representation of a Stack as a Linked List. – C | C++ | Java
Infix to Postfix Conversion – C | C++ | Java
Infix to prefix conversion in – C | C++ | Java
Postfix to Prefix Conversion in – C | C++ | Java

Queues

Queues in Data Structures (Introduction)
Queues Program in C and implementation
Implementation of Queues using Arrays | C Program
Types of Queues in Data Structure
Application of Queue Data Structure
Insertion in Queues Program (Enqueuing) – C | C++ | Java
Deletion (Removal) in Queues Program(Dequeuing) – C | C++ | Java
Reverse a Queue – C | C++ | Java
Queues using Linked Lists – C | C++ | Java
Implement Queue using Stack – C | C++ | Java
Implement Queue using two Stacks – C | C++ | Java

Circular Queues

Circular queue in Data Structure
Applications of Circular Queues
Circular queue in – C | C++ | Java
Circular queue using Array – C | C++ | Java
Circular Queue using Linked Lists – C | C++ | Java

Priority Queue

Application of Priority Queue
Priority Queue Example
Priority Queue Introduction – C | C++ | Java
Priority Queue Implementation using Array – C | C++ | Java
Priority Queue using Linked List – C | C++ | Java
Priority Queue Insertion and Deletion- C | C++ | Java