Reversing a Queue using Recursion

Difficulty Level Easy
Queue Recursion Technical ScripterViews 234

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

Table of Contents

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

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
queue.add(curr);
}

public static void main(String[] args) {
// Example 1
Queue<Integer> q1 = new LinkedList<>();
q1.add(10);
q1.add(9);
q1.add(3);
q1.add(11);
q1.add(5);
reverseQueue(q1);
for (Integer i : q1) {
System.out.print(i + " ");
}
System.out.println();

// Example 2
Queue<Integer> q2 = new LinkedList<>();
q2.add(1);
q2.add(2);
q2.add(3);
q2.add(4);
q2.add(5);
q2.add(6);
q2.add(7);
q2.add(8);
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

Translate »