Reversing a Queue: Using Stack
We know that a queue is a FIFO structure, and random access of elements is not allowed, so it is not possible to reverse the queue in-place so we need another data structure in which we could store the elements of the queue in such a manner that while inserting the elements back to the queue the order of elements is reversed. So our aim is to find a data structure that could help in reversing a queue and has a property of LIFO(Last In First Out). Do you know such a data structure?
You guessed it right! Stack is the data structure that can fulfill our requirement and help us to reverse the queue. So in this approach for reversing a queue, we will dequeue all the elements of the queue and push them into the stack, and once the queue is empty, we will pop elements from the stack and insert them in the queue.
Code:
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
void reverse(queue<int> &q)
{
// Explicitly create a stack.
stack<int> st;
// Push all elements of the queue into the stack.
while (!q.empty())
{
st.push(q.front());
q.pop();
}
// Push back all elements from the stack into the queue.
while (!st.empty())
{
q.push(st.top());
st.pop();
}
}
void printQueue(queue<int> q)
{
while(!q.empty())
{
cout<<q.front()<<" ";
q.pop();
}
cout<<endl;
}
int main()
{
queue<int> q;
//inserting elements into the queue using loop
for(int i=1;i<=10;i++)
{
q.push(i);
}
cout<<"Queue before Reversing: ";
printQueue(q);
reverse(q);
cout<<"Queue after Reversing: ";
printQueue(q);
}
You can also try this code with Online C++ Compiler
Output:
Queue before Reversing: 1 2 3 4 5 6 7 8 9 10
Queue after Reversing: 10 9 8 7 6 5 4 3 2 1
You can also try this code with Online C++ Compiler
Time Complexity: O(n) where n is the size of the queue as we are iterating the queue once.
Space Complexity: O(n) as we are storing the elements of the queue in the stack.
Also see, Introduction to C#
Must Read Recursion in Data Structure
Reversing a Queue: Using Recursion
In this approach, instead of creating a stack explicitly, we will use the concept of Recursion. The idea is to remove the front element from the queue and recursively call the reverse function for the remaining queue. In this way, we are dividing the larger problem into smaller sub-problems. We will pop the elements from the queue until it becomes empty, which is our base condition for a recursive function.
Once the queue is empty, push the elements back into the queue in this way, we will be able to reverse the elements as in the recursive function stack, the element that was popped at last would be pushed first and would be at the front of the queue.
Code:
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
void reverse(queue < int > & q) {
if (q.empty()) {
// If the queue is empty, return.
return;
}
// Store the front element in a variable.
int element = q.front();
q.pop();
// Recursively call for the rest of the queue.
reverse(q);
// Push back the stored element.
q.push(element);
}
void printQueue(queue<int> q)
{
while(!q.empty())
{
cout<<q.front()<<" ";
q.pop();
}
cout<<endl;
}
int main()
{
queue<int> q;
for(int i=1;i<=10;i++)
{
q.push(i);
}
cout<<"Queue before Reversing: ";
printQueue(q);
reverse(q);
cout<<"Queue after Reversing: ";
printQueue(q);
}
You can also try this code with Online C++ Compiler
Output:
Queue before Reversing: 1 2 3 4 5 6 7 8 9 10
Queue after Reversing: 10 9 8 7 6 5 4 3 2 1
You can also try this code with Online C++ Compiler
Time Complexity: O(n) where n is the size of the queue as we make the recursive calls for each element once and perform operations in constant time.
Space Complexity: O(n) if we consider the function call stack else O(1).
Read about Application of Queue in Data Structure here.
You can also read about the topic - hash function in data structure
Conclusion
This blog covered the various methods of reversing a queue. We discussed two approaches for reversing a queue, namely: Using stack and Using recursion. The blog discusses approaches with algorithms and code in C++.
Recommended Readings:
Don't stop here. Check out our Data Structures and Algorithms -guided path to learn DSA from scratch. We hope you found this blog useful. If you want to solve more problems like this which have been asked in the interviews, big tech giants like Amazon, Flipkart, Google, and Facebook, you can look out for interview problems at Coding Ninjas Studio.
83+ registered 