Home Â» Technical Interview Questions Â» Queue Interview Questions Â» Reversing a Queue

# Reversing a Queue

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

READ  Implementation of Deque using circular array

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

## JAVA Code for Reversing a Queue

```import java.util.LinkedList;
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

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup