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 <bits/stdc++.h> 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<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> reverseQueue(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 = reverseQueue(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(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).
leave a comment
0 Comments