# Reversing a Queue

Difficulty Level Easy
Frequently asked in Accolite Coursera Delhivery Factset GreyOrange Zoho
Larsen & Toubro Queue StackViews 330

In Reversing a Queue problem we have given a queue, write an algorithm to reverse the queue.

## Examples

Input
queue = 10 -> 8 -> 4 -> 23
Output
queue = 23->4->8->10

Input
queue = 11 -> 98 -> 31 -> 42 -> 73 -> 6
Output
queue = 6 -> 73 -> 42 -> 31 -> 98 -> 11

Input
queue = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Output
queue = 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

## Algorithm for Reversing a Queue

A queue can be reversed by using a stack,

1. Remove all the elements from the queue and push them to a stack.
2. Pop-out all the elements from the stack and push them back to the queue.
3. The queue is revered, print the elements of the queue.

## Explanation for Reversing a Queue

Consider an example,
queue =10 -> 8 -> 4 -> 23

Step 1

One by one remove elements from the queue and push them into a stack.
queue =10 -> 8 -> 4 -> 23 and stack= null
Iteration 1
queue = 8 -> 4 -> 23 and stack= 10
Iteration 2
queue = 4 -> 23 and stack = 8 -> 10
Iteration 3
queue = 23 and stack= 4 -> 8 -> 23
Iteration 4
queue = null and stack = 23->4->8->23

Step 2

Pop out all the elements from the stack and push them back to the queue.
queue = null and stack = 23 -> 4 -> 8 -> 10
Iteration 1
queue = 23 and stack= 4 -> 8 -> 10
Iteration 2
queue = 23 -> 4 and stack = 8 -> 10
Iteration 3
queue = 23 -> 4 -> 8 and stack = 10
Iteration 4
queue = 23 -> 4 -> 8 -> 10 and stack = null

The queue is reversed. See the image below for clarification.

## JAVA Code for Reversing a Queue

import java.util.Queue;
import java.util.Stack;

public class ReversingAQueue {
private static void reverseQueue(Queue<Integer> queue) {
int n = queue.size();

Stack<Integer> stack = new Stack<>();
// Remove all the elements from queue and push them to stack
for (int i = 0; i < n; i++) {
int curr = queue.poll();
stack.push(curr);
}

// Pop out elements from the stack and push them back to queue
for (int i = 0; i < n; i++) {
int curr = stack.pop();
}

// Print the reversed queue
for (Integer i : queue) {
System.out.print(i + " ");
}
System.out.println();
}

public static void main(String[] args) {
// Example 1
reverseQueue(q1);

// Example 2
reverseQueue(q2);
}
}
23 4 8 10
6 73 42 31 98 11

## C++ Code for Reversing a Queue

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

void reverseQueue(queue<int> &queue) {
int n = queue.size();

stack<int> st;
// Remove all the elements from queue and push them to stack
for (int i = 0; i < n; i++) {
int curr = queue.front();
queue.pop();
st.push(curr);
}

// Pop out elements from the stack and push them back to queue
for (int i = 0; i < n; i++) {
int curr = st.top();
st.pop();
queue.push(curr);
}

// Print the reversed queue
for (int i = 0; i < n; i++) {
int curr = queue.front();
queue.pop();
cout<<curr<<" ";
queue.push(curr);
}
cout<<endl;
}

int main() {
// Example 1
queue<int> q1;
int k1 = 3;
q1.push(10);
q1.push(8);
q1.push(4);
q1.push(23);
reverseQueue(q1);

// Example 2
queue<int> q2;
int k2 = 2;
q2.push(11);
q2.push(98);
q2.push(31);
q2.push(42);
q2.push(73);
q2.push(6);
reverseQueue(q2);
}
23 4 8 10
6 73 42 31 98 11

## Complexity Analysis

Time Complexity = O(n)
Space Complexity = O(n)
where n is the number of nodes in the queue.

References

Translate »