Reverse queue using recursion
This code addresses the problem of reversing the elements of a queue using recursion. A queue is a linear data structure that follows the First In First Out (FIFO) principle, where the element added first is the one that will be removed first. In this context, the code aims to reverse the order of elements within the queue using a recursive approach.
Problem Statement
The task is to reverse the order of elements within a given queue using a recursive method. The program should take a queue of integers as input and output the queue with its elements reversed using recursion.
Example
Given a queue with elements [2, 3, 6, 1, 9, 8], the output of the program should display the reversed queue: [8, 9, 1, 6, 3, 2].
Solution Idea
The solution involves using a recursive approach to reverse the elements of the queue. The basic idea is to remove the front element of the queue, recursively reverse the remaining elements, and then add the removed element to the back of the reversed queue.
Pseudocode
display_queue(record):
if record is empty:
return
other = new queue
while record is not empty:
data = front element of record
push data into other
pop front element from record
while other is not empty:
data = front element of other
print data
pop front element from other
push data into record
reverse_queue(record):
if record is empty:
return
else:
data = front element of record
pop front element from record
reverse_queue(record)
push data into record
Algorithm Explanation
- The
display_queue
function takes a queue as input and displays its elements while preserving the original order. It does this by copying the elements to another queue, displaying them, and then adding them back to the original queue. - The
reverse_queue
function reverses the elements of the queue using a recursive approach. It removes the front element, recursively reverses the remaining elements, and then adds the removed element to the back of the reversed queue.
Code Solution
// C++ program for
// Reverse queue using recursion
#include <iostream>
#include <queue>
using namespace std;
// Display queue elements
// Here used one extra queue to store actual queue element
void display_queue(queue <int> & record)
{
if (record.size() == 0)
{
//When queue is empty
return;
}
queue <int> other;
int data = 0;
// Copy Queue elements into new queue
while (record.size() > 0)
{
//Get front element
data = record.front();
other.push(data);
record.pop();
}
// Display queue element
while (other.size() > 0)
{
//Get front element
data = other.front();
cout << " " << data;
other.pop();
//Add element back to actual queue
record.push(data);
}
cout << endl;
}
//Reverse a queue elements
void reverse_queue(queue <int> & record)
{
if (record.size() == 0)
{
//When queue is empty
return;
}
else
{
//Get front element
int data = record.front();
//Remove a element of queue
record.pop();
//Recursive execute function
reverse_queue(record);
//Add back to queue
record.push(data);
}
}
int main()
{
//Define a queue of integer elements
queue <int> record;
//Add queue elements
record.push(2);
record.push(3);
record.push(6);
record.push(1);
record.push(9);
record.push(8);
cout << "\n Before Reverse element : ";
display_queue(record);
reverse_queue(record);
cout << "\n After Reverse element : ";
display_queue(record);
return 0;
}
Output
Before Reverse element : 2 3 6 1 9 8
After Reverse element : 8 9 1 6 3 2
//Java Program
//Reverse queue using recursion
import java.util.Queue;
import java.util.LinkedList;
class ReverseQueue
{
public Queue < Integer > record;
public ReverseQueue()
{
record = new LinkedList < > ();
}
// Display queue elements
// Here used one extra queue to store actual queue element
public void display_queue()
{
if (this.record.size() == 0)
{
//When queue is empty
return;
}
Queue < Integer > other = new LinkedList <> ();
int data = 0;
// Copy Queue elements into new queue
while (this.record.size() > 0)
{
//Get front element
data = this.record.peek();
other.add(data);
this.record.remove();
}
// Display queue element
while (other.size() > 0)
{
//Get front element
data = other.peek();
System.out.print(" " + data);
other.remove();
//Add element back to actual queue
this.record.add(data);
}
System.out.print("\n");
}
//Reverse a queue elements
public void reverse_queue()
{
if (this.record.size() == 0)
{
//When queue is empty
return;
}
else
{
//Get front element
int data = this.record.peek();
//Remove a element of queue
this.record.remove();
//Recursive execute function
reverse_queue();
//Add back to queue
this.record.add(data);
}
}
public void add_record()
{
//Add Queue elements
this.record.add(2);
this.record.add(3);
this.record.add(6);
this.record.add(1);
this.record.add(9);
this.record.add(8);
}
public static void main(String[] args)
{
ReverseQueue obj = new ReverseQueue();
obj.add_record();
//Before
System.out.print("\n Before Reverse element : ");
obj.display_queue();
obj.reverse_queue();
//After
System.out.print("\n After Reverse element : ");
obj.display_queue();
}
}
Output
Before Reverse element : 2 3 6 1 9 8
After Reverse element : 8 9 1 6 3 2
//Include namespace system
using System;
using System.Collections;
// Reverse queue using recursion
class ReverseQueue
{
public Queue record = null;
public ReverseQueue()
{
record = new Queue();
}
//Display queue elements
public void display_queue()
{
if (this.record.Count == 0)
{
return;
}
// Display Queue Elements
foreach(var element in this.record)
{
Console.Write(" {0}",element);
}
}
//Reverse a queue elements
public void reverse_queue()
{
if (record.Count == 0)
{
//When queue is empty
return;
}
else
{
int data = (int) record.Peek();
//Remove front element of queue
this.record.Dequeue();
reverse_queue();
//append data into queue
this.record.Enqueue(data);
}
}
public void add_record()
{
//Add queue elements
this.record.Enqueue(2);
this.record.Enqueue(3);
this.record.Enqueue(6);
this.record.Enqueue(1);
this.record.Enqueue(9);
this.record.Enqueue(8);
}
public static void Main(String[] args)
{
ReverseQueue obj = new ReverseQueue();
obj.add_record();
//Before
Console.Write("\n Before Reverse element : ");
obj.display_queue();
//Reverse Element
obj.reverse_queue();
//After
Console.Write("\n After Reverse element : ");
obj.display_queue();
}
}
Output
Before Reverse element : 2 3 6 1 9 8
After Reverse element : 8 9 1 6 3 2
<?php
// Php Program
// Reverse queue using recursion
class ReverseQueue
{
public $record;
function __construct()
{
//Create a custom queue
$this->record = array();
}
public function enqueue($data)
{
//Add element at end of queue
array_push($this->record,$data);
}
public function dequeue()
{
// Check whether queue array is empty or not
if (count($this->record) == 0)
{
// When try of remove a element in empty queue
echo ("Queue Empty");
return;
}
else
{
array_shift($this->record);
}
}
public function peek() {
// Check whether queue array is empty or not
if (count($this->record)==0)
{
// When try of remove a element in empty queue
echo ("Queue Empty");
} else
{
return $this->record[0];
}
}
//Display queue elements
public function display_queue()
{
if (count($this->record) == 0)
{
return;
}
for ($i=0; $i < count($this->record) ; $i++)
{
echo " ".$this->record[$i];
}
}
//Reverse a queue elements
public function reverse_queue()
{
if (count($this->record) == 0)
{
//When queue is empty
return;
}
else
{
$data = $this->peek();
//Remove front element of queue
$this->dequeue();
$this->reverse_queue();
//append data into queue
$this->enqueue($data);
}
}
public function add_record()
{
//Add queue elements
$this->enqueue(2);
$this->enqueue(3);
$this->enqueue(6);
$this->enqueue(1);
$this->enqueue(9);
$this->enqueue(8);
}
}
function main()
{
$obj = new ReverseQueue();
$obj->add_record();
echo "\n Before Queue element : ";
$obj->display_queue();
//Reverse Element
$obj->reverse_queue();
echo "\n After Queue element : ";
$obj->display_queue();
}
main();
Output
Before Queue element : 2 3 6 1 9 8
After Queue element : 8 9 1 6 3 2
// Node JS program for
// Reverse queue using recursion
class ReverseQueue
{
constructor()
{
this.record = [];
}
//Display queue elements
display_queue()
{
if (this.record.length == 0)
{
return;
}
for (var i = 0; i < this.record.length; i++)
{
console.log(this.record[i]);
}
}
peek()
{
if (this.record.length == 0)
{
return;
}
else
{
return this.record[0];
}
}
dequeue()
{
if (this.record.length == 0)
{
//When queue is empty
return;
}
else
{
this.record.shift();
}
}
//Reverse a queue elements
reverse_queue()
{
if (this.record.length == 0)
{
//When queue is empty
return;
}
else
{
var data = this.peek();
//Remove front element of queue
this.dequeue();
this.reverse_queue();
//append data into queue
this.record.push(data);
}
}
add_record()
{
//Add queue elements
this.record.push(2);
this.record.push(3);
this.record.push(6);
this.record.push(1);
this.record.push(9);
this.record.push(8);
}
}
function main()
{
var obj = new ReverseQueue();
obj.add_record();
console.log("\n Before Reverse element : ");
obj.display_queue();
//Reverse Element
obj.reverse_queue();
console.log("\n After Reverse element : ");
obj.display_queue();
}
main();
Output
Before Reverse element :
2
3
6
1
9
8
After Reverse element :
8
9
1
6
3
2
Output Explanation
The output first displays the original queue: [2, 3, 6, 1, 9, 8]. After calling the reverse_queue
function, the reversed queue is displayed: [8, 9, 1, 6, 3, 2].
Time Complexity
The time complexity of the algorithm is O(N), where N is the number of elements in the queue. This is because each element is removed from the queue and added back during the reversal process, and this happens for each element in the queue.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment