# Reversing a queue using recursion

Given a queue, write a recursive function to reverse it.
Standard operations allowed :
enqueue(x) : Add an item x to rear of queue.
dequeue() : Remove an item from front of queue.
empty() : Checks if a queue is empty or not.

Examples :

```Input : Q = [5, 24, 9, 6, 8, 4, 1, 8, 3, 6]
Output : Q = [6, 3, 8, 1, 4, 8, 6, 9, 24, 5]

Explanation : Output queue is the reverse of the input queue.

Input : Q = [8, 7, 2, 5, 1]
Output : Q = [1, 5, 2, 7, 8]
```

Recursive Algorithm :
1) Pop element from the queue if the queue has elements otherwise return empty queue.
2) Call reverseQueue function for the remaining queue.
3) Push the popped element in the resultant reversed queue.

Pseudo Code :

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

## C++

 `// C++ code for reversing a queue ` `#include ` `using` `namespace` `std; ` ` `  `// Utility function to print the queue ` `void` `printQueue(queue<``long` `long` `int``> Queue) ` `{ ` `    ``while` `(!Queue.empty()) { ` `        ``cout << Queue.front() << ``" "``; ` `        ``Queue.pop(); ` `    ``} ` `} ` ` `  `// Recursive function to reverse the queue ` `void` `reverseQueue(queue<``long` `long` `int``>& q) ` `{ ` `    ``// Base case ` `    ``if` `(q.empty()) ` `        ``return``; ` ` `  `    ``// Dequeue current item (from front)   ` `    ``long` `long` `int` `data = q.front(); ` `    ``q.pop(); ` ` `  `    ``// Reverse remaining queue   ` `    ``reverseQueue(q); ` ` `  `    ``// Enqueue current item (to rear)   ` `    ``q.push(data); ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``queue<``long` `long` `int``> Queue; ` `    ``Queue.push(56); ` `    ``Queue.push(27); ` `    ``Queue.push(30); ` `    ``Queue.push(45); ` `    ``Queue.push(85); ` `    ``Queue.push(92); ` `    ``Queue.push(58); ` `    ``Queue.push(80); ` `    ``Queue.push(90); ` `    ``Queue.push(100); ` `    ``reverseQueue(Queue); ` `    ``printQueue(Queue); ` `} `

## Java

 `// 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 ` `public` `class` `Queue_reverse { ` `  `  `    ``static` `Queue 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 reverseQueue(Queue q) ` `{ ` `    ``// Base case ` `    ``if` `(q.isEmpty()) ` `        ``return` `q; ` ` `  `    ``// Dequeue current item (from front)   ` `    ``int` `data = q.peek(); ` `    ``q.remove(); ` ` `  `    ``// Reverse remaining queue   ` `    ``q = reverseQueue(q); ` ` `  `    ``// Enqueue current item (to rear)   ` `    ``q.add(data); ` `         `  `    ``return` `q; ` `} ` `  `  `// Driver code ` `public` `static` `void` `main(String args[]) ` `{ ` `    ``queue = ``new` `LinkedList(); ` `    ``queue.add(``56``); ` `    ``queue.add(``27``); ` `    ``queue.add(``30``); ` `    ``queue.add(``45``); ` `    ``queue.add(``85``); ` `    ``queue.add(``92``); ` `    ``queue.add(``58``); ` `    ``queue.add(``80``); ` `    ``queue.add(``90``); ` `    ``queue.add(``100``); ` `    ``queue = reverseQueue(queue); ` `    ``Print(); ` `} ` `} `

## Python3

 `# Queue Class ` `class` `Queue: ` `    ``def` `__init__(``self``): ` `        ``self``.items ``=` `[] ` ` `  ` `  `    ``def` `isEmpty(``self``): ` `        ``return` `self``.items ``=``=` `[] ` ` `  `    ``def` `add(``self``, item): ` `        ``self``.items.append(item) ` ` `  `    ``def` `pop(``self``): ` `        ``return` `self``.items.pop(``0``) ` ` `  `    ``def` `front(``self``): ` `        ``return` `self``.items[``0``] ` ` `  `    ``def` `printQueue(``self``): ` `        ``for` `i ``in` `self``.items: ` `            ``print``(i, end ``=``" "``) ` `        ``print``("") ` ` `  ` `  `# Recursive Function to reverse the queue ` `def` `reverseQueue(q): ` ` `  `    ``# Base case ` `    ``if` `(q.isEmpty()): ` `        ``return` ` `  `    ``# Dequeue current item (from front)  ` `    ``data ``=` `q.front(); ` `    ``q.pop(); ` ` `  `    ``# Reverse remaining queue   ` `    ``reverseQueue(q) ` ` `  `    ``# Enqueue current item (to rear)   ` `    ``q.add(data) ` ` `  ` `  `# Driver Code ` `q ``=` `Queue() ` `q.add(``56``) ` `q.add(``27``) ` `q.add(``30``) ` `q.add(``45``) ` `q.add(``85``) ` `q.add(``92``) ` `q.add(``58``) ` `q.add(``80``) ` `q.add(``90``) ` `q.add(``100``) ` `reverseQueue(q) ` `q.printQueue() `

## C#

 `// C# code for reversing a queue ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `class` `GFG ` `{ ` `    ``// Utility function  ` `    ``// to print the queue ` `    ``static` `void` `printQueue(Queue<``long``> queue) ` `    ``{ ` `        ``while` `(queue.Count != 0)  ` `        ``{ ` `            ``Console.Write(queue.Peek() + ``" "``); ` `            ``queue.Dequeue(); ` `        ``} ` `    ``} ` `     `  `    ``// Recursive function  ` `    ``// to reverse the queue ` `    ``static` `void` `reverseQueue(``ref` `Queue<``long``> q) ` `    ``{ ` `        ``// Base case ` `        ``if` `(q.Count == 0) ` `            ``return``; ` `     `  `        ``// Dequeue current  ` `        ``// item (from front)  ` `        ``long` `data = q.Peek(); ` `        ``q.Dequeue(); ` `     `  `        ``// Reverse remaining queue  ` `        ``reverseQueue(``ref` `q); ` `     `  `        ``// Enqueue current ` `        ``// item (to rear)  ` `        ``q.Enqueue(data); ` `    ``}      ` `     `  `    ``// Driver code ` `    ``static` `void` `Main() ` `    ``{ ` `        ``Queue<``long``> queue = ``new` `Queue<``long``>(); ` `        ``queue.Enqueue(56); ` `        ``queue.Enqueue(27); ` `        ``queue.Enqueue(30); ` `        ``queue.Enqueue(45); ` `        ``queue.Enqueue(85); ` `        ``queue.Enqueue(92); ` `        ``queue.Enqueue(58); ` `        ``queue.Enqueue(80); ` `        ``queue.Enqueue(90); ` `        ``queue.Enqueue(100); ` `        ``reverseQueue(``ref` `queue); ` `        ``printQueue(queue); ` `    ``} ` `} ` ` `  `// This code is contributed by  ` `// Manish Shaw(manishshaw1) `

Output:

```100 90 80 58 92 85 45 30 27 56
```

Time Complexity : O(n).