Posted on by Kalkicode
Code Stack

Reverse a queue using stack

The problem is to reverse a queue using a stack. The goal is to reverse the order of elements in the queue such that the front element becomes the rear element, the second element becomes the second-to-last element, and so on.

Example

Let's consider a queue with elements: 1, 2, 3, 4, 5, 9, 11. After reversing the queue, the elements will be: 11, 9, 5, 4, 3, 2, 1.

Idea to Solve the Problem

To reverse the queue using a stack, we will follow these steps:

  1. Create a custom stack data structure with push, pop, and isEmpty operations.
  2. Create a custom queue data structure with enqueue and dequeue operations.
  3. Traverse the queue and push each element onto the stack.
  4. After pushing all elements onto the stack, pop each element from the stack and enqueue it back into the queue.
  5. The order of elements in the queue will be reversed.

Algorithm

  1. Define a structure for the queue node struct MyQueue, containing an integer data value and a pointer to the next node.
  2. Define a structure for the stack node struct MyStack, containing a pointer to the queue node and a pointer to the next node.
  3. Define global pointers head and tail for the queue, and top for the stack, initialized to NULL.
  4. Create a function enqueue to add elements to the queue. If the queue is empty, set both head and tail to the new node; otherwise, add the new node to the tail.
  5. Create a function dequeue to remove and return elements from the queue. If the queue is not empty, remove the head node, update the head, and return the data value of the removed node.
  6. Create a function push to add elements to the stack. Create a new stack node and set its element to the provided queue node. Then push the new node onto the stack.
  7. Create a function pop to remove and return elements from the stack. If the stack is not empty, remove the top node, extract the queue node it contains, free the stack node, and return the queue node.
  8. Create a function reverse to reverse the queue using the stack. Traverse the queue, push each element onto the stack, and set the next pointer of each queue node to NULL. Then pop elements from the stack and enqueue them back into the queue, setting head and tail appropriately.
  9. In the main function, create a sample queue, display its elements, reverse it using the reverse function, and then display the reversed elements.

Pseudocode

FUNCTION enqueue(value):
    node = new MyQueue
    node.data = value
    node.next = NULL
    IF head is NULL:
        head = node
        tail = node
    ELSE:
        tail.next = node
        tail = node

FUNCTION dequeue():
    IF head is NULL:
        PRINT "Empty Queue"
        RETURN -1
    ELSE:
        temp = head
        data = temp.data
        head = head.next
        IF head is NULL:
            tail = NULL
        free(temp)
        RETURN data

FUNCTION push(node):
    new_node = new MyStack
    new_node.element = node
    new_node.next = top
    top = new_node

FUNCTION pop():
    IF top is not NULL:
        result = top.element
        temp = top
        top = top.next
        free(temp)
        RETURN result

FUNCTION reverse():
    temp = head
    WHILE head is not NULL:
        push(head)
        head = head.next
        temp.next = NULL
    WHILE top is not NULL:
        IF head is NULL:
            head = pop()
            tail = head
        ELSE:
            tail.next = pop()
            tail = tail.next

FUNCTION print_queue():
    temp = head
    WHILE temp is not NULL:
        PRINT temp.data
        temp = temp.next

FUNCTION main():
    enqueue(1)
    enqueue(2)
    enqueue(3)
    enqueue(4)
    enqueue(5)
    enqueue(9)
    enqueue(11)
    PRINT "Before :"
    print_queue()
    reverse()
    PRINT "After :"
    print_queue()

Code Solution

Here given code implementation process.

//C Program
//Reverse a queue using stack
#include <stdio.h>

#include <stdlib.h> //for malloc function

//Create structure of Queue
struct MyQueue
{
	int data;
	struct MyQueue *next;
};
struct MyStack
{
	struct MyQueue *element;
	struct MyStack *next;
};
// Define some global variables which is directly 
// will be accessed within below defined function.
// Queue pointer variables.
struct MyQueue *head = NULL, *tail = NULL;
//Stack pointer variable
struct MyStack *top = NULL;
//This function are add new element into queue
void enqueue(int value)
{
	//Create a dynamic node
	struct MyQueue *node = (struct MyQueue *) malloc(sizeof(struct MyQueue));
	if (node == NULL)
	{
		printf("Memory overflow\n");
	}
	else
	{
		//set new node data
		node->data = value;
		node->next = NULL;
		if (head == NULL)
		{
			//add first element into queue
			head = node;
			tail = node;
		}
		else
		{
			//add node at the end using tail pointer
			tail->next = node;
			tail = node;
		}
	}
}
//Delete a element into queue
int dequeue()
{
	int data = -1;
	if (head == NULL)
	{
		printf("Empty Queue\n");
		return data;
	}
	//Get the deleted node
	struct MyQueue *temp = head;
	data = temp->data;
	//visit to next node of queue
	head = head->next;
	if (head == NULL)
	{
		//When deleting a last node of linked list
		tail = NULL;
	}
	free(temp);
	temp = NULL;
	return data;
}
void push(struct MyQueue *node)
{
	struct MyStack *new_node = (struct MyStack *) malloc(sizeof(struct MyStack));
	if (new_node)
	{
		new_node->element = node;
		new_node->next = top;
		top = new_node;
	}
}
// This function are remove top node into stack and return 
// the queue element .
// Basically we are returns a value of data value but here added 
// a actual queue element into stack. 
// so return this node element
struct MyQueue *pop()
{
	if (top != NULL)
	{
		struct MyQueue *result = top->element;
		struct MyStack *temp = top;
		top->element = NULL;
		top = top->next;
		free(temp);
		temp = NULL;
		return result;
	}
	return NULL;
}
//Display all queue element
void print_queue()
{
	struct MyQueue *temp = head;
	while (temp != NULL)
	{
		printf("%d  ", temp->data);
		temp = temp->next;
	}
	printf("\n");
}
//This method are reverse the queue elements 
void reverse()
{
	struct MyQueue *temp = head;
	//First add all queue elements into stack
	while (head != NULL)
	{
		temp = head;
		//add current head node into stack
		push(head);
		//visit to next upcoming node
		head = head->next;
		//Note that we are not delete queue element 
		// so added element are hold next node information to queue 
		// so remove next node information
		// set nil
		temp->next = NULL;
	}
	//add stack elements into the actual queue
	while (top != NULL)
	{
		if (head == NULL)
		{
			// pop a stack element
			// And set that top queue element as first node of queue
			head = pop();
			// Because that is first node of queue.
			// So tail node is also hold the information of first node.
			tail = head;
		}
		else
		{
			//Add new stack top element into queue tail section
			tail->next = pop();
			//make a new tail node
			tail = tail->next;
		}
	}
}
int main()
{
	//Add queue elements
	enqueue(1);
	enqueue(2);
	enqueue(3);
	enqueue(4);
	enqueue(5);
	enqueue(9);
	enqueue(11);
  	printf("Before : ");
	//Display all queue elements
	print_queue();
	reverse();
  	printf("After : ");
	//Display all queue elements
	print_queue();
	return 0;
}

Output

Before : 1  2  3  4  5  9  11
After : 11  9  5  4  3  2  1
/*
	Java Program
	Reverse a queue using stack
*/
//Create structure of Queue
class MyQueue
{
	public int data;
	public MyQueue next;
	//set new node value
	public MyQueue(int element)
	{
		this.data = element;
		this.next = null;
	}
}
class MyStack
{
	public MyQueue element;
	public MyStack next;
	//set new node data
	public MyStack(MyQueue element)
	{
		this.element = element;
		this.next = null;
	}
}
class Process
{
	public MyStack top;
	public MyQueue head;
	public MyQueue tail;
	public Process()
	{
		this.top = null;
		this.head = null;
		this.tail = null;
	}
	//This function are add new element into queue
	public void enqueue(int value)
	{
		//Create a dynamic node
		MyQueue node = new MyQueue(value);
		if (node == null)
		{
			System.out.print("Memory overflow\n");
		}
		else
		{
			if (this.head == null)
			{
				//add first element into queue
				this.head = node;
				this.tail = node;
			}
			else
			{
				//add node at the end using tail pointer
				this.tail.next = node;
				this.tail = node;
			}
		}
	}
	//Delete a element into queue
	public int dequeue()
	{
		int data = -1;
		if (this.head == null)
		{
			System.out.print("Empty Queue\n");
			return data;
		}
		//Get the deleted node
		MyQueue temp = this.head;
		data = temp.data;
		//visit to next node of queue
		this.head = this.head.next;
		if (this.head == null)
		{
			//When deleting a last node of linked list
			this.tail = null;
		}
		temp = null;
		return data;
	}
	// Add Queue element into the stack
	public void push(MyQueue node)
	{
		MyStack new_node = new MyStack(node);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
		}
	}
	// This function are remove top node into stack and return 
	// the queue element .
	// Basically we are returns a value of data value but here added 
	// a actual queue element into stack. 
	// so return this node element
	public MyQueue pop()
	{
		if (this.top != null)
		{
			MyQueue result = this.top.element;
			MyStack temp = this.top;
			this.top.element = null;
			this.top = this.top.next;
			temp = null;
			return result;
		}
		return null;
	}
	//Display all queue element
	public void print_queue()
	{
		MyQueue temp = head;
		while (temp != null)
		{
			System.out.print(" " + temp.data + " ");
			temp = temp.next;
		}
		System.out.print("\n");
	}
	//This method are reverse the queue elements 
	public void reverse()
	{
		MyQueue temp = null;
		//First add all queue elements into stack
		while (this.head != null)
		{
			temp = this.head;
			// add current head node into stack
			this.push(this.head);
			// visit to next upcoming node
			this.head = this.head.next;
			// Note that we are not delete queue element 
			// so added element are hold next node information to queue 
			// so remove next node information
			// set nil
			temp.next = null;
		}
		//add stack elements into the actual queue
		while (this.top != null)
		{
			if (this.head == null)
			{
				// pop a stack element
				// And set that top queue element as first node of queue
				this.head = this.pop();
				// Because that is first node of queue.
				// So tail node is also hold the information of first node.
				this.tail = this.head;
			}
			else
			{
				//Add new stack top element into queue tail section
				this.tail.next = this.pop();
				//make a new tail node
				this.tail = this.tail.next;
			}
		}
	}
	public static void main(String[] args)
	{
		Process obj = new Process();
		//Add queue elements
		obj.enqueue(1);
		obj.enqueue(2);
		obj.enqueue(3);
		obj.enqueue(4);
		obj.enqueue(5);
		obj.enqueue(9);
		obj.enqueue(11);
		//Display all queue elements
		obj.print_queue();
		obj.reverse();
		//Display all queue elements
		obj.print_queue();
	}
}

Output

 1  2  3  4  5  9  11
 11  9  5  4  3  2  1
//Include header file
#include <iostream>

using namespace std;
/*
	C++ Program
	Reverse a queue using stack
*/
//Create structure of Queue
class MyQueue
{
	public: int data;
	MyQueue * next;
	//set new node value
	MyQueue(int element)
	{
		this->data = element;
		this->next = NULL;
	}
};
class MyStack
{
	public: MyQueue * element;
	MyStack * next;
	//set new node data
	MyStack(MyQueue * element)
	{
		this->element = element;
		this->next = NULL;
	}
};
class Process
{
	public: MyStack * top;
	MyQueue * head;
	MyQueue * tail;
	Process()
	{
		this->top = NULL;
		this->head = NULL;
		this->tail = NULL;
	}
	//This function are add new element into queue
	void enqueue(int value)
	{
		//Create a dynamic node
		MyQueue * node = new MyQueue(value);
		if (node == NULL)
		{
			cout << "Memory overflow\n";
		}
		else
		{
			if (this->head == NULL)
			{
				//add first element into queue
				this->head = node;
				this->tail = node;
			}
			else
			{
				//add node at the end using tail pointer
				this->tail->next = node;
				this->tail = node;
			}
		}
	}
	//Delete a element into queue
	int dequeue()
	{
		int data = -1;
		if (this->head == NULL)
		{
			cout << "Empty Queue\n";
			return data;
		}
		//Get the deleted node
		MyQueue * temp = this->head;
		data = temp->data;
		//visit to next node of queue
		this->head = this->head->next;
		if (this->head == NULL)
		{
			//When deleting a last node of linked list
			this->tail = NULL;
		}
		temp = NULL;
		return data;
	}
	// Add Queue element into the stack
	void push(MyQueue * node)
	{
		MyStack * new_node = new MyStack(node);
		if (new_node != NULL)
		{
			new_node->next = this->top;
			this->top = new_node;
		}
	}
	// This function are remove top node into stack and return 
	// the queue element .
	// Basically we are returns a value of data value but here added 
	// a actual queue element into stack. 
	// so return this node element
	MyQueue * pop()
	{
		if (this->top != NULL)
		{
			MyQueue * result = this->top->element;
			MyStack * temp = this->top;
			this->top->element = NULL;
			this->top = this->top->next;
			temp = NULL;
			return result;
		}
		return NULL;
	}
	//Display all queue element
	void print_queue()
	{
		MyQueue * temp = this->head;
		while (temp != NULL)
		{
			cout << " " << temp->data << " ";
			temp = temp->next;
		}
		cout << "\n";
	}
	//This method are reverse the queue elements 
	void reverse()
	{
		MyQueue * temp = NULL;
		//First add all queue elements into stack
		while (this->head != NULL)
		{
			temp = this->head;
			// add current head node into stack
			this->push(this->head);
			// visit to next upcoming node
			this->head = this->head->next;
			// Note that we are not delete queue element 
			// so added element are hold next node information to queue 
			// so remove next node information
			// set nil
			temp->next = NULL;
		}
		//add stack elements into the actual queue
		while (this->top != NULL)
		{
			if (this->head == NULL)
			{
				// pop a stack element
				// And set that top queue element as first node of queue
				this->head = this->pop();
				// Because that is first node of queue.
				// So tail node is also hold the information of first node.
				this->tail = this->head;
			}
			else
			{
				//Add new stack top element into queue tail section
				this->tail->next = this->pop();
				//make a new tail node
				this->tail = this->tail->next;
			}
		}
	}
};
int main()
{
	Process obj = Process();
	//Add queue elements
	obj.enqueue(1);
	obj.enqueue(2);
	obj.enqueue(3);
	obj.enqueue(4);
	obj.enqueue(5);
	obj.enqueue(9);
	obj.enqueue(11);
	//Display all queue elements
	obj.print_queue();
	obj.reverse();
	//Display all queue elements
	obj.print_queue();
	return 0;
}

Output

 1  2  3  4  5  9  11
 11  9  5  4  3  2  1
//Include namespace system
using System;
/*
	C# Program
	Reverse a queue using stack
*/
//Create structure of Queue
class MyQueue
{
	public int data;
	public MyQueue next;
	//set new node value
	public MyQueue(int element)
	{
		this.data = element;
		this.next = null;
	}
}
class MyStack
{
	public MyQueue element;
	public MyStack next;
	//set new node data
	public MyStack(MyQueue element)
	{
		this.element = element;
		this.next = null;
	}
}
class Process
{
	public MyStack top;
	public MyQueue head;
	public MyQueue tail;
	public Process()
	{
		this.top = null;
		this.head = null;
		this.tail = null;
	}
	//This function are add new element into queue
	public void enqueue(int value)
	{
		//Create a dynamic node
		MyQueue node = new MyQueue(value);
		if (node == null)
		{
			Console.Write("Memory overflow\n");
		}
		else
		{
			if (this.head == null)
			{
				//add first element into queue
				this.head = node;
				this.tail = node;
			}
			else
			{
				//add node at the end using tail pointer
				this.tail.next = node;
				this.tail = node;
			}
		}
	}
	//Delete a element into queue
	public int dequeue()
	{
		int data = -1;
		if (this.head == null)
		{
			Console.Write("Empty Queue\n");
			return data;
		}
		//Get the deleted node
		MyQueue temp = this.head;
		data = temp.data;
		//visit to next node of queue
		this.head = this.head.next;
		if (this.head == null)
		{
			//When deleting a last node of linked list
			this.tail = null;
		}
		temp = null;
		return data;
	}
	// Add Queue element into the stack
	public void push(MyQueue node)
	{
		MyStack new_node = new MyStack(node);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
		}
	}
	// This function are remove top node into stack and return 
	// the queue element .
	// Basically we are returns a value of data value but here added 
	// a actual queue element into stack. 
	// so return this node element
	public MyQueue pop()
	{
		if (this.top != null)
		{
			MyQueue result = this.top.element;
			this.top.element = null;
			this.top = this.top.next;
			return result;
		}
		return null;
	}
	//Display all queue element
	public void print_queue()
	{
		MyQueue temp = head;
		while (temp != null)
		{
			Console.Write(" " + temp.data + " ");
			temp = temp.next;
		}
		Console.Write("\n");
	}
	//This method are reverse the queue elements 
	public void reverse()
	{
		MyQueue temp = null;
		//First add all queue elements into stack
		while (this.head != null)
		{
			temp = this.head;
			// add current head node into stack
			this.push(this.head);
			// visit to next upcoming node
			this.head = this.head.next;
			// Note that we are not delete queue element 
			// so added element are hold next node information to queue 
			// so remove next node information
			// set nil
			temp.next = null;
		}
		//add stack elements into the actual queue
		while (this.top != null)
		{
			if (this.head == null)
			{
				// pop a stack element
				// And set that top queue element as first node of queue
				this.head = this.pop();
				// Because that is first node of queue.
				// So tail node is also hold the information of first node.
				this.tail = this.head;
			}
			else
			{
				//Add new stack top element into queue tail section
				this.tail.next = this.pop();
				//make a new tail node
				this.tail = this.tail.next;
			}
		}
	}
	public static void Main(String[] args)
	{
		Process obj = new Process();
		//Add queue elements
		obj.enqueue(1);
		obj.enqueue(2);
		obj.enqueue(3);
		obj.enqueue(4);
		obj.enqueue(5);
		obj.enqueue(9);
		obj.enqueue(11);
		//Display all queue elements
		obj.print_queue();
		obj.reverse();
		//Display all queue elements
		obj.print_queue();
	}
}

Output

 1  2  3  4  5  9  11
 11  9  5  4  3  2  1
<?php
/*
	Php Program
	Reverse a queue using stack
*/
//Create structure of Queue
class MyQueue
{
	public $data;
	public $next;
	//set new node value
	function __construct($element)
	{
		$this->data = $element;
		$this->next = null;
	}
}
class MyStack
{
	public $element;
	public $next;
	//set new node data
	function __construct($element)
	{
		$this->element = $element;
		$this->next = null;
	}
}
class Process
{
	public $top;
	public $head;
	public $tail;

	function __construct()
	{
		$this->top = null;
		$this->head = null;
		$this->tail = null;
	}
	//This function are add new element into queue
	public	function enqueue($value)
	{
		//Create a dynamic node
		$node = new MyQueue($value);
		if ($node == null)
		{
			echo "Memory overflow\n";
		}
		else
		{
			if ($this->head == null)
			{
				//add first element into queue
				$this->head = $node;
				$this->tail = $node;
			}
			else
			{
				//add node at the end using tail pointer
				$this->tail->next = $node;
				$this->tail = $node;
			}
		}
	}
	//Delete a element into queue
	public	function dequeue()
	{
		$data = -1;
		if ($this->head == null)
		{
			echo "Empty Queue\n";
			return $data;
		}
		//Get the deleted node
		$temp = $this->head;
		$data = $temp->data;
		//visit to next node of queue
		$this->head = $this->head->next;
		if ($this->head == null)
		{
			//When deleting a last node of linked list
			$this->tail = null;
		}
		$temp = null;
		return $data;
	}
	// Add Queue element into the stack
	public	function push($node)
	{
		$new_node = new MyStack($node);
		if ($new_node != null)
		{
			$new_node->next = $this->top;
			$this->top = $new_node;
		}
	}
	// This function are remove top node into stack and return 
	// the queue element .
	// Basically we are returns a value of data value but here added 
	// a actual queue element into stack. 
	// so return this node element
	public	function pop()
	{
		if ($this->top != null)
		{
			$result = $this->top->element;
			$temp = $this->top;
			$this->top->element = null;
			$this->top = $this->top->next;
			$temp = null;
			return $result;
		}
		return null;
	}
	//Display all queue element
	public	function print_queue()
	{
		$temp = $this->head;
		while ($temp != null)
		{
			echo " ". $temp->data ." ";
			$temp = $temp->next;
		}
		echo "\n";
	}
	//This method are reverse the queue elements 
	public	function reverse()
	{
		$temp = null;
		//First add all queue elements into stack
		while ($this->head != null)
		{
			$temp = $this->head;
			// add current head node into stack
			$this->push($this->head);
			// visit to next upcoming node
			$this->head = $this->head->next;
			// Note that we are not delete queue element 
			// so added element are hold next node information to queue 
			// so remove next node information
			// set nil
			$temp->next = null;
		}
		//add stack elements into the actual queue
		while ($this->top != null)
		{
			if ($this->head == null)
			{
				// pop a stack element
				// And set that top queue element as first node of queue
				$this->head = $this->pop();
				// Because that is first node of queue.
				// So tail node is also hold the information of first node.
				$this->tail = $this->head;
			}
			else
			{
				//Add new stack top element into queue tail section
				$this->tail->next = $this->pop();
				//make a new tail node
				$this->tail = $this->tail->next;
			}
		}
	}
}

function main()
{
	$obj = new Process();
	//Add queue elements
	$obj->enqueue(1);
	$obj->enqueue(2);
	$obj->enqueue(3);
	$obj->enqueue(4);
	$obj->enqueue(5);
	$obj->enqueue(9);
	$obj->enqueue(11);
	//Display all queue elements
	$obj->print_queue();
	$obj->reverse();
	//Display all queue elements
	$obj->print_queue();
}
main();

Output

 1  2  3  4  5  9  11
 11  9  5  4  3  2  1
/*
	Node Js Program
	Reverse a queue using stack
*/
//Create structure of Queue
class MyQueue
{
	//set new node value
	constructor(element)
	{
		this.data = element;
		this.next = null;
	}
}
class MyStack
{
	//set new node data
	constructor(element)
	{
		this.element = element;
		this.next = null;
	}
}
class Process
{
	constructor()
	{
		this.top = null;
		this.head = null;
		this.tail = null;
	}
	//This function are add new element into queue
	enqueue(value)
	{
		//Create a dynamic node
		var node = new MyQueue(value);
		if (node == null)
		{
			process.stdout.write("Memory overflow\n");
		}
		else
		{
			if (this.head == null)
			{
				//add first element into queue
				this.head = node;
				this.tail = node;
			}
			else
			{
				//add node at the end using tail pointer
				this.tail.next = node;
				this.tail = node;
			}
		}
	}
	//Delete a element into queue
	dequeue()
	{
		this.data = -1;
		if (this.head == null)
		{
			process.stdout.write("Empty Queue\n");
			return data;
		}
		//Get the deleted node
		var temp = this.head;
		data = temp.data;
		//visit to next node of queue
		this.head = this.head.next;
		if (this.head == null)
		{
			//When deleting a last node of linked list
			this.tail = null;
		}
		temp = null;
		return data;
	}
	// Add Queue element into the stack
	push(node)
	{
		var new_node = new MyStack(node);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
		}
	}
	// This function are remove top node into stack and return 
	// the queue element .
	// Basically we are returns a value of data value but here added 
	// a actual queue element into stack. 
	// so return this node element
	pop()
	{
		if (this.top != null)
		{
			var result = this.top.element;
			var temp = this.top;
			this.top.element = null;
			this.top = this.top.next;
			temp = null;
			return result;
		}
		return null;
	}
	//Display all queue element
	print_queue()
	{
		var temp = this.head;
		while (temp != null)
		{
			process.stdout.write(" " + temp.data + " ");
			temp = temp.next;
		}
		process.stdout.write("\n");
	}
	//This method are reverse the queue elements 
	reverse()
	{
		var temp = null;
		//First add all queue elements into stack
		while (this.head != null)
		{
			temp = this.head;
			// add current head node into stack
			this.push(this.head);
			// visit to next upcoming node
			this.head = this.head.next;
			// Note that we are not delete queue element 
			// so added element are hold next node information to queue 
			// so remove next node information
			// set nil
			temp.next = null;
		}
		//add stack elements into the actual queue
		while (this.top != null)
		{
			if (this.head == null)
			{
				// pop a stack element
				// And set that top queue element as first node of queue
				this.head = this.pop();
				// Because that is first node of queue.
				// So tail node is also hold the information of first node.
				this.tail = this.head;
			}
			else
			{
				//Add new stack top element into queue tail section
				this.tail.next = this.pop();
				//make a new tail node
				this.tail = this.tail.next;
			}
		}
	}
}

function main()
{
	var obj = new Process();
	//Add queue elements
	obj.enqueue(1);
	obj.enqueue(2);
	obj.enqueue(3);
	obj.enqueue(4);
	obj.enqueue(5);
	obj.enqueue(9);
	obj.enqueue(11);
	//Display all queue elements
	obj.print_queue();
	obj.reverse();
	//Display all queue elements
	obj.print_queue();
}
main();

Output

 1  2  3  4  5  9  11
 11  9  5  4  3  2  1
# 	Python 3 Program
# 	Reverse a queue using stack

# Create structure of Queue
class MyQueue :
	
	# set new node value
	def __init__(self, element) :
		self.data = element
		self.next = None
	

class MyStack :
	
	# set new node data
	def __init__(self, element) :
		self.element = element
		self.next = None
	

class Process :
	
	def __init__(self) :
		self.top = None
		self.head = None
		self.tail = None
	
	# This function are add new element into queue
	def enqueue(self, value) :
		# Create a dynamic node
		node = MyQueue(value)
		if (node == None) :
			print("Memory overflow\n", end = "")
		else :
			if (self.head == None) :
				# add first element into queue
				self.head = node
				self.tail = node
			else :
				# add node at the end using tail pointer
				self.tail.next = node
				self.tail = node
			
		
	
	# Delete a element into queue
	def dequeue(self) :
		self.data = -1
		if (self.head == None) :
			print("Empty Queue\n", end = "")
			return data
		
		# Get the deleted node
		temp = self.head
		data = temp.data
		# visit to next node of queue
		self.head = self.head.next
		if (self.head == None) :
			# When deleting a last node of linked list
			self.tail = None
		
		temp = None
		return data
	
	#  Add Queue element into the stack
	def push(self, node) :
		new_node = MyStack(node)
		if (new_node != None) :
			new_node.next = self.top
			self.top = new_node
		
	
	#  This function are remove top node into stack and return 
	#  the queue element .
	#  Basically we are returns a value of data value but here added 
	#  a actual queue element into stack. 
	#  so return this node element
	def pop(self) :
		if (self.top != None) :
			result = self.top.element
			temp = self.top
			self.top.element = None
			self.top = self.top.next
			temp = None
			return result
		
		return None
	
	# Display all queue element
	def print_queue(self) :
		temp = self.head
		while (temp != None) :
			print(" ", temp.data ," ", end = "")
			temp = temp.next
		
		print("\n", end = "")
	
	# This method are reverse the queue elements 
	def reverse(self) :
		temp = None
		# First add all queue elements into stack
		while (self.head != None) :
			temp = self.head
			#  add current head node into stack
			self.push(self.head)
			#  visit to next upcoming node
			self.head = self.head.next
			#  Note that we are not delete queue element 
			#  so added element are hold next node information to queue 
			#  so remove next node information
			#  set nil
			temp.next = None
		
		# add stack elements into the actual queue
		while (self.top != None) :
			if (self.head == None) :
				#  pop a stack element
				#  And set that top queue element as first node of queue
				self.head = self.pop()
				#  Because that is first node of queue.
				#  So tail node is also hold the information of first node.
				self.tail = self.head
			else :
				# Add new stack top element into queue tail section
				self.tail.next = self.pop()
				# make a new tail node
				self.tail = self.tail.next
			
		
	

def main() :
	obj = Process()
	# Add queue elements
	obj.enqueue(1)
	obj.enqueue(2)
	obj.enqueue(3)
	obj.enqueue(4)
	obj.enqueue(5)
	obj.enqueue(9)
	obj.enqueue(11)
	# Display all queue elements
	obj.print_queue()
	obj.reverse()
	# Display all queue elements
	obj.print_queue()

if __name__ == "__main__": main()

Output

  1    2    3    4    5    9    11
  11    9    5    4    3    2    1
# 	Ruby Program
# 	Reverse a queue using stack

# Create structure of Queue
class MyQueue 

	# Define the accessor and reader of class MyQueue  
	attr_reader :data, :next
	attr_accessor :data, :next

	# set new node value
	def initialize(element)
	
		self.data = element
		self.next = nil
	end
end
class MyStack 

	# Define the accessor and reader of class MyStack  
	attr_reader :element, :next
	attr_accessor :element, :next

	# set new node data
	def initialize(element)
	
		self.element = element
		self.next = nil
	end
end
class ProcessRun 

	# Define the accessor and reader of class Process  
	attr_reader :top, :head, :tail
	attr_accessor :top, :head, :tail

	def initialize()
	
		self.top = nil
		self.head = nil
		self.tail = nil
	end
	# This function are add new element into queue
	def enqueue(value)
	
		# Create a dynamic node
		node = MyQueue.new(value)
		if (node == nil)
		
			print("Memory overflow\n")
		else
		
			if (self.head == nil)
			
				# add first element into queue
				self.head = node
				self.tail = node
			else
			
				# add node at the end using tail pointer
				self.tail.next = node
				self.tail = node
			end
		end
	end
	# Delete a element into queue
	def dequeue()
	
		@data = -1
		if (self.head == nil)
		
			print("Empty Queue\n")
			return data
		end
		# Get the deleted node
		temp = self.head
		data = temp.data
		# visit to next node of queue
		self.head = self.head.next
		if (self.head == nil)
		
			# When deleting a last node of linked list
			self.tail = nil
		end
		temp = nil
		return data
	end
	#  Add Queue element into the stack
	def push(node)
	
		new_node = MyStack.new(node)
		if (new_node != nil)
		
			new_node.next = self.top
			self.top = new_node
		end
	end
	#  This function are remove top node into stack and return 
	#  the queue element .
	#  Basically we are returns a value of data value but here added 
	#  a actual queue element into stack. 
	#  so return this node element
	def pop()
	
		if (self.top != nil)
		
			result = self.top.element
			temp = self.top
			self.top.element = nil
			self.top = self.top.next
			temp = nil
			return result
		end
		return nil
	end
	# Display all queue element
	def print_queue()
	
		temp = @head
		while (temp != nil)
		
			print(" ", temp.data ," ")
			temp = temp.next
		end
		print("\n")
	end
	# This method are reverse the queue elements 
	def reverse()
	
		temp = nil
		# First add all queue elements into stack
		while (self.head != nil)
		
			temp = self.head
			#  add current head node into stack
			self.push(self.head)
			#  visit to next upcoming node
			self.head = self.head.next
			#  Note that we are not delete queue element 
			#  so added element are hold next node information to queue 
			#  so remove next node information
			#  set nil
			temp.next = nil
		end
		# add stack elements into the actual queue
		while (self.top != nil)
		
			if (self.head == nil)
			
				#  pop a stack element
				#  And set that top queue element as first node of queue
				self.head = self.pop()
				#  Because that is first node of queue.
				#  So tail node is also hold the information of first node.
				self.tail = self.head
			else
			
				# Add new stack top element into queue tail section
				self.tail.next = self.pop()
				# make a new tail node
				self.tail = self.tail.next
			end
		end
	end
end
def main()

	obj = ProcessRun.new()
	# Add queue elements
	obj.enqueue(1)
	obj.enqueue(2)
	obj.enqueue(3)
	obj.enqueue(4)
	obj.enqueue(5)
	obj.enqueue(9)
	obj.enqueue(11)
	# Display all queue elements
	obj.print_queue()
	obj.reverse()
	# Display all queue elements
	obj.print_queue()
end
main()

Output

 1  2  3  4  5  9  11 
 11  9  5  4  3  2  1 
/*
	Scala Program
	Reverse a queue using stack
*/
//Create structure of Queue
class MyQueue(var data: Int,
	var next: MyQueue)
{
	//set new node value
	def this(element: Int)
	{
		this(element,null);
	}
}
class MyStack(var element: MyQueue,
	var next: MyStack)
{
	//set new node data
	def this(element: MyQueue)
	{
		this(element,null);
	}
}
class Process(var top: MyStack,
	var head: MyQueue,
		var tail: MyQueue)
{
	def this()
	{
		this(null,null,null);
	}
	//This function are add new element into queue
	def enqueue(value: Int): Unit = {
		//Create a dynamic node
		var node: MyQueue = new MyQueue(value);
		if (node == null)
		{
			print("Memory overflow\n");
		}
		else
		{
			if (this.head == null)
			{
				//add first element into queue
				this.head = node;
				this.tail = node;
			}
			else
			{
				//add node at the end using tail pointer
				this.tail.next = node;
				this.tail = node;
			}
		}
	}
	//Delete a element into queue
	def dequeue(): Int = {
		var data: Int = -1;
		if (this.head == null)
		{
			print("Empty Queue\n");
			return data;
		}
		//Get the deleted node
		var temp: MyQueue = this.head;
		data = temp.data;
		//visit to next node of queue
		this.head = this.head.next;
		if (this.head == null)
		{
			//When deleting a last node of linked list
			this.tail = null;
		}
		temp = null;
		return data;
	}
	// Add Queue element into the stack
	def push(node: MyQueue): Unit = {
		var new_node: MyStack = new MyStack(node);
		if (new_node != null)
		{
			new_node.next = this.top;
			this.top = new_node;
		}
	}
	// This function are remove top node into stack and return 
	// the queue element .
	// Basically we are returns a value of data value but here added 
	// a actual queue element into stack. 
	// so return this node element
	def pop(): MyQueue = {
		if (this.top != null)
		{
			var result: MyQueue = this.top.element;
			var temp: MyStack = this.top;
			this.top.element = null;
			this.top = this.top.next;
			temp = null;
			return result;
		}
		return null;
	}
	//Display all queue element
	def print_queue(): Unit = {
		var temp: MyQueue = head;
		while (temp != null)
		{
			print(" " + temp.data + " ");
			temp = temp.next;
		}
		print("\n");
	}
	//This method are reverse the queue elements 
	def reverse(): Unit = {
		var temp: MyQueue = null;
		//First add all queue elements into stack
		while (this.head != null)
		{
			temp = this.head;
			// add current head node into stack
			this.push(this.head);
			// visit to next upcoming node
			this.head = this.head.next;
			// Note that we are not delete queue element 
			// so added element are hold next node information to queue 
			// so remove next node information
			// set nil
			temp.next = null;
		}
		//add stack elements into the actual queue
		while (this.top != null)
		{
			if (this.head == null)
			{
				// pop a stack element
				// And set that top queue element as first node of queue
				this.head = this.pop();
				// Because that is first node of queue.
				// So tail node is also hold the information of first node.
				this.tail = this.head;
			}
			else
			{
				//Add new stack top element into queue tail section
				this.tail.next = this.pop();
				//make a new tail node
				this.tail = this.tail.next;
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: Process = new Process();
		//Add queue elements
		obj.enqueue(1);
		obj.enqueue(2);
		obj.enqueue(3);
		obj.enqueue(4);
		obj.enqueue(5);
		obj.enqueue(9);
		obj.enqueue(11);
		//Display all queue elements
		obj.print_queue();
		obj.reverse();
		//Display all queue elements
		obj.print_queue();
	}
}

Output

 1  2  3  4  5  9  11
 11  9  5  4  3  2  1
/*
	Swift Program
	Reverse a queue using stack
*/
//Create structure of Queue
class MyQueue
{
	var data: Int;
	var next: MyQueue? ;
	//set new node value
	init(_ element: Int)
	{
		self.data = element;
		self.next = nil;
	}
}
class MyStack
{
	var element: MyQueue? ;
	var next: MyStack? ;
	//set new node data
	init(_ element: MyQueue? )
	{
		self.element = element;
		self.next = nil;
	}
}
class Process
{
	var top: MyStack? ;
	var head: MyQueue? ;
	var tail: MyQueue? ;
	init()
	{
		self.top = nil;
		self.head = nil;
		self.tail = nil;
	}
	//This function are add new element into queue
	func enqueue(_ value: Int)
	{
		//Create a dynamic node
		let node: MyQueue? = MyQueue(value);
		if (node == nil)
		{
			print("Memory overflow\n", terminator: "");
		}
		else
		{
			if (self.head == nil)
			{
				//add first element into queue
				self.head = node;
				self.tail = node;
			}
			else
			{
				//add node at the end using tail pointer
				self.tail!.next = node;
				self.tail = node;
			}
		}
	}
	//Delete a element into queue
	func dequeue() -> Int
	{
		var data: Int = -1;
		if (self.head == nil)
		{
			print("Empty Queue\n", terminator: "");
			return data;
		}
		//Get the deleted node
		var temp: MyQueue? = self.head;
		data = temp!.data;
		//visit to next node of queue
		self.head = self.head!.next;
		if (self.head == nil)
		{
			//When deleting a last node of linked list
			self.tail = nil;
		}
		temp = nil;
		return data;
	}
	// Add Queue element into the stack
	func push(_ node: MyQueue? )
	{
		let new_node: MyStack? = MyStack(node);
		if (new_node != nil)
		{
			new_node!.next = self.top;
			self.top = new_node;
		}
	}
	// This function are remove top node into stack and return 
	// the queue element .
	// Basically we are returns a value of data value but here added 
	// a actual queue element into stack. 
	// so return this node element
	func pop() -> MyQueue?
	{
		if (self.top != nil)
		{
			let result: MyQueue? = self.top!.element;
			self.top!.element = nil;
			self.top = self.top!.next;
			return result;
		}
		return nil;
	}
	//Display all queue element
	func print_queue()
	{
		var temp: MyQueue? = self.head;
		while (temp != nil)
		{
			print(" ", temp!.data ," ", terminator: "");
			temp = temp!.next;
		}
		print("\n", terminator: "");
	}
	//This method are reverse the queue elements 
	func reverse()
	{
		var temp: MyQueue? = nil;
		//First add all queue elements into stack
		while (self.head != nil)
		{
			temp = self.head;
			// add current head node into stack
			self.push(self.head);
			// visit to next upcoming node
			self.head = self.head!.next;
			// Note that we are not delete queue element 
			// so added element are hold next node information to queue 
			// so remove next node information
			// set nil
			temp!.next = nil;
		}
		//add stack elements into the actual queue
		while (self.top != nil)
		{
			if (self.head == nil)
			{
				// pop a stack element
				// And set that top queue element as first node of queue
				self.head = self.pop();
				// Because that is first node of queue.
				// So tail node is also hold the information of first node.
				self.tail = self.head;
			}
			else
			{
				//Add new stack top element into queue tail section
				self.tail!.next = self.pop();
				//make a new tail node
				self.tail = self.tail!.next;
			}
		}
	}
}
func main()
{
	let obj: Process = Process();
	//Add queue elements
	obj.enqueue(1);
	obj.enqueue(2);
	obj.enqueue(3);
	obj.enqueue(4);
	obj.enqueue(5);
	obj.enqueue(9);
	obj.enqueue(11);
	//Display all queue elements
	obj.print_queue();
	obj.reverse();
	//Display all queue elements
	obj.print_queue();
}
main();

Output

  1    2    3    4    5    9    11
  11    9    5    4    3    2    1

Time Complexity Analysis

  1. Enqueue operation has a time complexity of O(1) as we simply add an element to the end of the queue.
  2. Dequeue operation has a time complexity of O(1) as we remove an element from the front of the queue.
  3. Push operation has a time complexity of O(1) as we simply add an element to the top of the stack.
  4. Pop operation has a time complexity of O(1) as we remove an element from the top of the stack.
  5. Reverse operation involves pushing all elements of the queue onto the stack (O(n)), and then popping all elements from the stack back into the queue (O(n)), giving a total time complexity of O(n).

Output Explanation

The output shows the elements of the queue before and after reversing using the reverse function. For example, "Before : 1 2 3 4 5 9 11" represents the original queue with elements 1, 2, 3, 4, 5, 9, and 11. After reversing, the queue becomes "After : 11 9 5 4 3 2 1", where the order of elements is reversed.

Comment

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