Reversing a Queue using Recursion  

Difficulty Level Easy
Queue Recursion Technical Scripter

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,

Please click Like if you loved this article?

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

See also
Implement Stack and Queue using Deque

Reversing a Queue using RecursionPin

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.

See also
Implementation of Deque using circular array

References

Please click Like if you loved this article?