Reversing Queue using Recursion

Last Updated on December 14, 2022 by Prepbytes

Problem Statement:

Given a queue, we have to make a recursive function to reverse it.

Queue:

A Queue is a linear data structure. Queue follows the FIFO rule i.e. First in First out. In other words we can say the element that goes in first is the element that comes out first.
For Example A ticket Queue outside a cinema hall where the person enters the queue first will get the ticket first.

Basic Operations of Queue:

• Enqueue: This operation is used to Insert an element at the end of the queue.
• Dequeue: This operation is used to remove and return an element from the front of the queue.
• isEmpty(): This operation is used to check whether the queue is empty or not.
• isFull(): This operation is used to check whether the queue is full or not.
• Peek(): This operation is used to get the value of the element from the front of the queue.

For reversing the queue, we will use the concept of recursion. The approach will firstly remove the front element from the queue and recursively call the reverse function for the remaining queue. By following this, we are dividing the larger problem into smaller sub-problems.

Example:
Input: Q = [15, 25, 3, 44, 55]
Output: Q = [55, 44, 3, 25, 15]
Explanation: Output queue is the reverse version of input queue.

Recursive Algorithm

1. Pop an element from the queue if the queue has elements otherwise return an empty queue.
2. Call the revQueue function for the remaining queue.
3. At last, Push the popped element in the resultant reversed queue.

Pseudo Code:

queue revQueue(queue)
{
    if (queue is empty)
       return queue;
    else {
       data = queue.front()
       queue.pop()
       queue = revQueue(queue);
       q.push(data);
       return queue;
    }
}

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

void printQueue(queue<long long int> Queue)
{
  while (!Queue.empty()) {
    cout << Queue.front() << " ";
    Queue.pop();
  }
}

void revQueue(queue<long long int>& q)
{
  if (q.empty())
    return;

  long long int data = q.front();
  q.pop();

  revQueue(q);

  q.push(data);
}

int main()
{
  queue<long long int> Queue;
  Queue.push(1);
  Queue.push(2);
  Queue.push(3);
  Queue.push(4);
  Queue.push(5);
  revQueue(Queue);
  printQueue(Queue);
}

// Java program to reverse a Queue by recursion
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

// Java program to reverse a queue recursively
 class Queue_reverse {

  static Queue<Integer> queue;

  // Utility function to print the queue
  static void Print()
  {
    while (!queue.isEmpty())
    {
      System.out.print(queue.peek() + " ");
      queue.remove();
    }
  }

// Recurrsive function to reverse the queue
static Queue<Integer> revQueue(Queue<Integer> q)
{
  // Base case
  if (q.isEmpty())
    return q;

  // Dequeue current item (from front)
  int data = q.peek();
  q.remove();

  // Reverse remaining queue
  q = revQueue(q);

  // Enqueue current item (to rear)
  q.add(data);
    
  return q;
}

// Driver code
public static void main(String args[])
{
  queue = new LinkedList<Integer>();
  queue.add(1);
  queue.add(2);
  queue.add(3);
  queue.add(4);
  queue.add(5);
  queue = revQueue(queue);
  Print();
}
}

from queue import Queue


def revQueue(queue: Queue):
  
  if queue.empty():
    return

  item = queue.queue[0]
  queue.get()

  revQueue(queue)

  queue.put(item)


def print_queue(queue: Queue):
  while not queue.empty():
    print(queue.queue[0], end=" ")
    queue.get()
  print()


if __name__ == "__main__":
  q = Queue()
  q.put(1)
  q.put(2)
  q.put(3)
  q.put(4)
  q.put(5)

  revQueue(q)
  print_queue(q)

Complexity:

Time Complexity: The time complexity of reversing a queue using a recursive function is O(n).
Space Complexity: The auxiliary space for reversing a queue using a recursive function will be O(n), as recursive function uses stack internally.

This article tried to discuss the concept of Reversing Queue using Recursion. Hope this blog helps you understand the concept. To practice problems you can check out MYCODE | Competitive Programming at Prepbytes