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

1. 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.
2. 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++
• Java
• C#
• Php
• Node Js

// 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;
}

 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();
	}
}

 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();
	}
}

 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();

 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();

 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.