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
tail = node
ELSE:
tail.next = node
tail = node

FUNCTION dequeue():
PRINT "Empty Queue"
RETURN -1
ELSE:
data = temp.data
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.next = NULL
WHILE top is not NULL:
ELSE:
tail.next = pop()
tail = tail.next

FUNCTION print_queue():
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;
{
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;
{
printf("Empty Queue\n");
return data;
}
//Get the deleted node
data = temp->data;
//visit to next node of queue
{
//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()
{
while (temp != NULL)
{
printf("%d  ", temp->data);
temp = temp->next;
}
printf("\n");
}
//This method are reverse the queue elements
void reverse()
{
//First add all queue elements into stack
{
//visit to next upcoming node
//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)
{
{
// pop a stack element
// And set that top queue element as first node of queue
// Because that is first node of queue.
// So tail node is also hold the information of first node.
}
else
{
//Add new stack top element into queue tail section
tail->next = pop();
//make a new tail node
tail = tail->next;
}
}
}
int main()
{
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 tail;
public Process()
{
this.top = 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
{
{
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;
{
System.out.print("Empty Queue\n");
return data;
}
//Get the deleted node
data = temp.data;
//visit to next node of queue
{
//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()
{
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
{
// visit to next upcoming node
// 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)
{
{
// pop a stack element
// And set that top queue element as first node of queue
// Because that is first node of queue.
// So tail node is also hold the information of first node.
}
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();
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 * tail;
Process()
{
this->top = 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
{
{
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;
{
cout << "Empty Queue\n";
return data;
}
//Get the deleted node
data = temp->data;
//visit to next node of queue
{
//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()
{
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
{
// visit to next upcoming node
// 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)
{
{
// pop a stack element
// And set that top queue element as first node of queue
// Because that is first node of queue.
// So tail node is also hold the information of first node.
}
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();
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 tail;
public Process()
{
this.top = 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
{
{
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;
{
Console.Write("Empty Queue\n");
return data;
}
//Get the deleted node
data = temp.data;
//visit to next node of queue
{
//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()
{
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
{
// visit to next upcoming node
// 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)
{
{
// pop a stack element
// And set that top queue element as first node of queue
// Because that is first node of queue.
// So tail node is also hold the information of first node.
}
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();
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 \$tail;

function __construct()
{
\$this->top = 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
{
{
\$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;
{
echo "Empty Queue\n";
return \$data;
}
//Get the deleted node
\$data = \$temp->data;
//visit to next node of queue
{
//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()
{
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
{
// visit to next upcoming node
// 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)
{
{
// pop a stack element
// And set that top queue element as first node of queue
// Because that is first node of queue.
// So tail node is also hold the information of first node.
}
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();
\$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.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
{
{
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;
{
process.stdout.write("Empty Queue\n");
return data;
}
//Get the deleted node
data = temp.data;
//visit to next node of queue
{
//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()
{
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
{
// visit to next upcoming node
// 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)
{
{
// pop a stack element
// And set that top queue element as first node of queue
// Because that is first node of queue.
// So tail node is also hold the information of first node.
}
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();
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.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 :
# add first element into queue
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
print("Empty Queue\n", end = "")
return data

# Get the deleted node
data = temp.data
# visit to next node of queue
# 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) :
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
#  visit to next upcoming node
#  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) :
#  pop a stack element
#  And set that top queue element as first node of queue
#  Because that is first node of queue.
#  So tail node is also hold the information of first node.
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()
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_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_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

def initialize()

self.top = 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

# add first element into queue
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

print("Empty Queue\n")
return data
end
# Get the deleted node
data = temp.data
# visit to next node of queue

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

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

#  visit to next upcoming node
#  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)

#  pop a stack element
#  And set that top queue element as first node of queue
#  Because that is first node of queue.
#  So tail node is also hold the information of first node.
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()
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 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
{
{
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;
{
print("Empty Queue\n");
return data;
}
//Get the deleted node
data = temp.data;
//visit to next node of queue
{
//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 = {
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
{
// visit to next upcoming node
// 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)
{
{
// pop a stack element
// And set that top queue element as first node of queue
// Because that is first node of queue.
// So tail node is also hold the information of first node.
}
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();
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 tail: MyQueue? ;
init()
{
self.top = 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
{
{
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;
{
print("Empty Queue\n", terminator: "");
return data;
}
//Get the deleted node
data = temp!.data;
//visit to next node of queue
{
//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()
{
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
{
// visit to next upcoming node
// 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)
{
{
// pop a stack element
// And set that top queue element as first node of queue
// Because that is first node of queue.
// So tail node is also hold the information of first node.
}
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();
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.

Categories
Relative Post