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

# Reversing a Queue using Recursion

In reversing a queue using recursion problem we have given a queue, write a recursive algorithm to reverse the queue using recursion.

## Examples

Input
10 -> 9 -> 3 -> 11 -> 5
Output
5 -> 11 -> 3 -> 9 -> 10

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

## Algorithm for Reversing a Queue using Recursion

Let us imagine that the function reverse(queue) is a recursive function that reverses the queue given to it. Its definition can be understood by an example,

queue = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
reverse(1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = reverse(2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) -> 1
reverse(2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = reverse(3 -> 4 -> 5 -> 6 -> 7 -> 8) -> 2
reverse(3 -> 4 -> 5 -> 6 -> 7 -> 8) = reverse(4 -> 5 -> 6 -> 7 -> 8) -> 3
reverse(4 -> 5 -> 6 -> 7 -> 8) = reverse(5 -> 6 -> 7 -> 8) -> 4
reverse(5 -> 6 -> 7 -> 8) = reverse(6 -> 7 -> 8) -> 5
reverse(6 -> 7 -> 8) = reverse(7 -> 8) -> 6
reverse(7 -> 8) = reverse(8) -> 7
reverse(8) = reverse() -> 8
reverse() = empty queue

So,
reverse(8) = 8
reverse(7 -> 8) = 8 -> 7
reverse(6 -> 7 -> 8) = 8 -> 7 -> 6
reverse(5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5
reverse(4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4
reverse(3 -> 4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4 -> 3
reverse(2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2
reverse(1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

READ  Find the First Circular Tour that visits all the Petrol Pumps

Base Case of recursion: The reverse of an empty queue is an empty queue.

1. If the queue is empty, return, else pop out the first element of the queue and store it in a variable, say curr.
2. Call the reverse method recursively on the remaining queue.
3. The reverse method will reverse the remaining queue, push the curr element to the queue.
4. The queue is reversed, prints its elements.

## JAVA Code for Reversing a Queue using Recursion

```import java.util.LinkedList;
import java.util.Queue;

public class ReversingAQueueUsingRecursion {
private static void reverseQueue(Queue<Integer> queue) {
// Base case
// reverse of an empty queue is an empty queue
if (queue.isEmpty()) {
return;
}

// remove an element from queue and store it in a variable, say curr
int curr = queue.poll();
// recursively call the reverseQueue method on remaining queue
reverseQueue(queue);
// add the removed element to the end of the reversed queue
}

public static void main(String[] args) {
// Example 1
reverseQueue(q1);
for (Integer i : q1) {
System.out.print(i + " ");
}
System.out.println();

// Example 2
reverseQueue(q2);
for (Integer i : q2) {
System.out.print(i + " ");
}
System.out.println();
}
}```
```5 11 3 9 10
8 7 6 5 4 3 2 1```

## C++ Code for Reversing a Queue using Recursion

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

void reverseQueue(queue<int> &q) {
// Base case
// reverse of an empty queue is an empty queue
if (q.empty()) {
return;
}

// remove an element from queue and store it in a variable, say curr
int curr = q.front();
q.pop();
// recursively call the reverseQueue method on remaining queue
reverseQueue(q);
// add the removed element to the end of the reversed queue
q.push(curr);
}

int main() {
// Example 1
queue<int> q1;
q1.push(10);
q1.push(9);
q1.push(3);
q1.push(11);
q1.push(5);
reverseQueue(q1);
while (!q1.empty()) {
cout<<q1.front()<<" ";
q1.pop();
}
cout<<endl;

// Example 2
queue<int> q2;
q2.push(1);
q2.push(2);
q2.push(3);
q2.push(4);
q2.push(5);
q2.push(6);
q2.push(7);
q2.push(8);
reverseQueue(q2);
while (!q2.empty()) {
cout<<q2.front()<<" ";
q2.pop();
}
cout<<endl;

return 0;
}```
```5 11 3 9 10
8 7 6 5 4 3 2 1```

## Complexity Analysis

Time Complexity = O(n)
Space Complexity = O(n), due to recursion which uses the stack concept.
where n is the number of elements in the queue.

References

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