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.
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.
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
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
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
Login/Signup to comment