Posted on by Kalkicode
Code Queue

# Append the elements of queue in mirror-inverse order

The problem at hand involves appending the elements of a queue in mirror-inverse order. In simpler terms, given a queue with elements, the goal is to reverse the order of its elements while maintaining the original sequence of elements within the mirrored pairs.

## Problem Statement

You are provided with a queue that supports basic operations such as enqueue (add), dequeue (remove), and peek (get the front element). The task is to implement a function that takes the queue and performs a mirror-inverse insertion of its elements, resulting in the queue containing its original elements followed by the same elements in reverse order.

## Example

Let's consider a queue with the following elements: 1, 4, 3.

After performing the mirror-inverse insertion, the queue would contain: 1, 4, 3, 3, 4, 1.

## Idea to Solve

The problem can be approached using a recursive approach. The idea is to recursively traverse the queue, appending each element to the end of the queue. This process ensures that elements are added in reverse order while maintaining their mirrored pairs.

## Pseudocode

``````mirrorInverse(queue, node):
if node is NULL:
return
mirrorInverse(queue, node.next)
enqueue(queue, node.key)``````

## Algorithm Explanation

1. The `mirrorInverse` function takes two arguments: the queue and the current node to be processed.
2. If the current node is NULL, the function returns.
3. The function first recursively calls itself with the next node.
4. Once the recursive calls return, the current node's key is appended to the end of the queue using the `enqueue` function.

## Code Solution

``````/*
C Program
Append the elements of queue in mirror-inverse order
*/
#include <stdio.h>
#include <stdlib.h>

struct QNode
{
int key;
struct QNode *next;
};
struct MyQueue
{
int size;
struct QNode *front;
struct QNode *rear;
};
struct MyQueue *makeQueue()
{
// Create dynamic node of MyQueue
struct MyQueue *q = (struct MyQueue *) malloc(sizeof(struct MyQueue));
if (q == NULL)
{
printf("\n Memory Overflow, when creating a new Queue\n");
}
else
{
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
return q;
}
// Returns the number of element in queue
int isSize(struct MyQueue *queue)
{
return queue->size;
}
// Returns the first element value
int peek(struct MyQueue *q)
{
if (isSize(q) == 0)
{
printf("\n Empty Queue");
return -1;
}
return q->front->key;
}
void enqueue(struct MyQueue *q, int key)
{
// Make a new Queue node
struct QNode *node = (struct QNode *) malloc(sizeof(struct QNode));
if (node != NULL)
{
// Set node values
node->key = key;
node->next = NULL;
if (q->front == NULL)
{
q->front = node;
q->rear = q->front;
}
else
{
q->rear->next = node;
q->rear = node;
}
q->size++;
}
else
{
printf("\nMemory Overflow, when creating a new Queue Node\n");
}
}
// Remove a queue elements
void dequeue(struct MyQueue *q)
{
if (isSize(q) > 0)
{
struct QNode *remove = q->front;
if (q->front == q->rear)
{
q->rear = NULL;
}
q->front = q->front->next;
q->size = q->size - 1;
remove->next = NULL;
//free node
free(remove);
remove = NULL;
}
}
//  Mirror-Inverse insertion at the end of queue
void mirrorInverse(struct MyQueue *q, struct QNode *node)
{
if (node == NULL)
{
return;
}
// Recursive approach to visit queue element
mirrorInverse(q, node->next);
// Append element at the end
enqueue(q, node->key);
}
// Display elements of queue
void display(struct MyQueue *q)
{
struct QNode *auxiliary = q->front;
// iterate the queue element
while (auxiliary != NULL)
{
// Display queue element
printf("  %d", auxiliary->key);
// Visit to next node
auxiliary = auxiliary->next;
}
printf("\n");
}
int main(int argc, char
const *argv[])
{
struct MyQueue *q = makeQueue();
enqueue(q, 1);
enqueue(q, 4);
enqueue(q, 3);
mirrorInverse(q, q->front);
display(q);
return 0;
}``````

#### Output

``  1  4  3  3  4  1``
``````/*
Java Program
Append the elements of queue in mirror-inverse order
*/
// Binary Tree node
class TreeNode
{
public int key;
public TreeNode left;
public TreeNode right;
public TreeNode(int key)
{
// Set node value
this.key = key;
this.left = null;
this.right = null;
}
}
// Queue Node
class QNode
{
public int key;
public QNode next;
public QNode(int key)
{
this.key = key;
this.next = null;
}
}
//Define custom queue class
class MyQueue
{
public QNode front;
public QNode rear;
public int size;
public MyQueue()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
public void enqueue(int n)
{
QNode node = new QNode(n);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last position
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
public int isSize()
{
return this.size;
}
public int peek()
{
if (this.isSize() == 0)
{
return -1;
}
else
{
return this.front.key;
}
}
}
public class Reflection
{
//  Mirror-Inverse insertion at the end of queue
public void mirrorInverse(MyQueue q, QNode node)
{
if (node == null)
{
return;
}
// Recursive approach to visit queue element
mirrorInverse(q, node.next);
// Append element at the end
q.enqueue(node.key);
}
// Display elements of queue
public void display(MyQueue q)
{
QNode auxiliary = q.front;
// iterate the queue element
while (auxiliary != null)
{
// Display queue element
System.out.print(" " + auxiliary.key);
// Visit to next node
auxiliary = auxiliary.next;
}
System.out.print("\n");
}
public static void main(String[] args)
{
MyQueue q = new MyQueue();
q.enqueue(1);
q.enqueue(4);
q.enqueue(3);
}
}``````

#### Output

`` 1 4 3 3 4 1``
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ Program
Append the elements of queue in mirror-inverse order
*/

// Binary Tree node
class TreeNode
{
public:
int key;
TreeNode *left;
TreeNode *right;
TreeNode(int key)
{
// Set node value
this->key = key;
this->left = NULL;
this->right = NULL;
}
};
// Queue Node
class QNode
{
public:
int key;
QNode *next;
QNode(int key)
{
this->key = key;
this->next = NULL;
}
};
//Define custom queue class
class MyQueue
{
public: QNode *front;
QNode *rear;
int size;
MyQueue()
{
this->front = NULL;
this->rear = NULL;
this->size = 0;
}
// Add a new node at last of queue
void enqueue(int n)
{
QNode *node = new QNode(n);
if (this->front == NULL)
{
// When first node of queue
this->front = node;
}
else
{
// Add node at last position
this->rear->next = node;
}
this->size++;
this->rear = node;
}
// Delete front node of queue
void dequeue()
{
if (this->front != NULL)
{
if (this->rear == this->front)
{
this->rear = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
}
this->size--;
}
}
int isSize()
{
return this->size;
}
int peek()
{
if (this->isSize() == 0)
{
return -1;
}
else
{
return this->front->key;
}
}
};
class Reflection
{
public:
//  Mirror-Inverse insertion at the end of queue
void mirrorInverse(MyQueue *q, QNode *node)
{
if (node == NULL)
{
return;
}
// Recursive approach to visit queue element
this->mirrorInverse(q, node->next);
// Append element at the end
q->enqueue(node->key);
}
// Display elements of queue
void display(MyQueue q)
{
QNode *auxiliary = q.front;
// iterate the queue element
while (auxiliary != NULL)
{
// Display queue element
cout << " " << auxiliary->key;
// Visit to next node
auxiliary = auxiliary->next;
}
cout << "\n";
}
};
int main()
{
MyQueue q = MyQueue();
q.enqueue(1);
q.enqueue(4);
q.enqueue(3);
return 0;
}``````

#### Output

`` 1 4 3 3 4 1``
``````// Include namespace system
using System;
/*
C# Program
Append the elements of queue in mirror-inverse order
*/
// Binary Tree node
public class TreeNode
{
public int key;
public TreeNode left;
public TreeNode right;
public TreeNode(int key)
{
// Set node value
this.key = key;
this.left = null;
this.right = null;
}
}
// Queue Node
public class QNode
{
public int key;
public QNode next;
public QNode(int key)
{
this.key = key;
this.next = null;
}
}
//Define custom queue class
public class MyQueue
{
public QNode front;
public QNode rear;
public int size;
public MyQueue()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
public void enqueue(int n)
{
QNode node = new QNode(n);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last position
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
public int isSize()
{
return this.size;
}
public int peek()
{
if (this.isSize() == 0)
{
return -1;
}
else
{
return this.front.key;
}
}
}
public class Reflection
{
//  Mirror-Inverse insertion at the end of queue
public void mirrorInverse(MyQueue q, QNode node)
{
if (node == null)
{
return;
}
// Recursive approach to visit queue element
mirrorInverse(q, node.next);
// Append element at the end
q.enqueue(node.key);
}
// Display elements of queue
public void display(MyQueue q)
{
QNode auxiliary = q.front;
// iterate the queue element
while (auxiliary != null)
{
// Display queue element
Console.Write(" " + auxiliary.key);
// Visit to next node
auxiliary = auxiliary.next;
}
Console.Write("\n");
}
public static void Main(String[] args)
{
MyQueue q = new MyQueue();
q.enqueue(1);
q.enqueue(4);
q.enqueue(3);
}
}``````

#### Output

`` 1 4 3 3 4 1``
``````<?php
/*
Php Program
Append the elements of queue in mirror-inverse order
*/
// Binary Tree node
class TreeNode
{
public \$key;
public \$left;
public \$right;

function __construct(\$key)
{
// Set node value
\$this->key = \$key;
\$this->left = null;
\$this->right = null;
}
}
// Queue Node
class QNode
{
public \$key;
public \$next;

function __construct(\$key)
{
\$this->key = \$key;
\$this->next = null;
}
}
//Define custom queue class
class MyQueue
{
public \$front;
public \$rear;
public \$size;

function __construct()
{
\$this->front = null;
\$this->rear = null;
\$this->size = 0;
}
// Add a new node at last of queue
public	function enqueue(\$n)
{
\$node = new QNode(\$n);
if (\$this->front == null)
{
// When first node of queue
\$this->front = \$node;
}
else
{
// Add node at last position
\$this->rear->next = \$node;
}
\$this->size++;
\$this->rear = \$node;
}
// Delete front node of queue
public	function dequeue()
{
if (\$this->front != null)
{
if (\$this->rear == \$this->front)
{
\$this->rear = null;
\$this->front = null;
}
else
{
\$this->front = \$this->front->next;
}
\$this->size--;
}
}
public	function isSize()
{
return \$this->size;
}
public	function peek()
{
if (\$this->isSize() == 0)
{
return -1;
}
else
{
return \$this->front->key;
}
}
}
class Reflections
{
//  Mirror-Inverse insertion at the end of queue
public	function mirrorInverse(\$q, \$node)
{
if (\$node == null)
{
return;
}
// Recursive approach to visit queue element
\$this->mirrorInverse(\$q, \$node->next);
// Append element at the end
\$q->enqueue(\$node->key);
}
// Display elements of queue
public	function display(\$q)
{
\$auxiliary = \$q->front;
// iterate the queue element
while (\$auxiliary != null)
{
// Display queue element
echo " ". \$auxiliary->key;
// Visit to next node
\$auxiliary = \$auxiliary->next;
}
echo "\n";
}
}

function main()
{
\$q = new MyQueue();
\$q->enqueue(1);
\$q->enqueue(4);
\$q->enqueue(3);
}
main();``````

#### Output

`` 1 4 3 3 4 1``
``````/*
Node Js Program
Append the elements of queue in mirror-inverse order
*/
// Binary Tree node
class TreeNode
{
constructor(key)
{
// Set node value
this.key = key;
this.left = null;
this.right = null;
}
}
// Queue Node
class QNode
{
constructor(key)
{
this.key = key;
this.next = null;
}
}
//Define custom queue class
class MyQueue
{
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
enqueue(n)
{
var node = new QNode(n);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last position
this.rear.next = node;
}
this.size++;
this.rear = node;
}
// Delete front node of queue
dequeue()
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size--;
}
}
isSize()
{
return this.size;
}
peek()
{
if (this.isSize() == 0)
{
return -1;
}
else
{
return this.front.key;
}
}
}
class Reflection
{
//  Mirror-Inverse insertion at the end of queue
mirrorInverse(q, node)
{
if (node == null)
{
return;
}
// Recursive approach to visit queue element
this.mirrorInverse(q, node.next);
// Append element at the end
q.enqueue(node.key);
}
// Display elements of queue
display(q)
{
var auxiliary = q.front;
// iterate the queue element
while (auxiliary != null)
{
// Display queue element
process.stdout.write(" " + auxiliary.key);
// Visit to next node
auxiliary = auxiliary.next;
}
process.stdout.write("\n");
}
}

function main()
{
var q = new MyQueue();
q.enqueue(1);
q.enqueue(4);
q.enqueue(3);
}
main();``````

#### Output

`` 1 4 3 3 4 1``
``````#  Python 3 Program
#  Append the elements of queue in mirror-inverse order

#  Binary Tree node
class TreeNode :

def __init__(self, key) :
#  Set node value
self.key = key
self.left = None
self.right = None

#  Queue Node
class QNode :

def __init__(self, key) :
self.key = key
self.next = None

# Define custom queue class
class MyQueue :

def __init__(self) :
self.front = None
self.rear = None
self.size = 0

#  Add a new node at last of queue
def enqueue(self, n) :
node = QNode(n)
if (self.front == None) :
#  When first node of queue
self.front = node
else :
#  Add node at last position
self.rear.next = node

self.size += 1
self.rear = node

#  Delete front node of queue
def dequeue(self) :
if (self.front != None) :
if (self.rear == self.front) :
self.rear = None
self.front = None
else :
self.front = self.front.next

self.size -= 1

def isSize(self) :
return self.size

def peek(self) :
if (self.isSize() == 0) :
return -1
else :
return self.front.key

class Reflection :
#   Mirror-Inverse insertion at the end of queue
def mirrorInverse(self, q, node) :
if (node == None) :
return

#  Recursive approach to visit queue element
self.mirrorInverse(q, node.next)
#  Append element at the end
q.enqueue(node.key)

#  Display elements of queue
def display(self, q) :
auxiliary = q.front
#  iterate the queue element
while (auxiliary != None) :
#  Display queue element
print(" ", auxiliary.key, end = "")
#  Visit to next node
auxiliary = auxiliary.next

print(end = "\n")

def main() :
q = MyQueue()
q.enqueue(1)
q.enqueue(4)
q.enqueue(3)

if __name__ == "__main__": main()``````

#### Output

``  1  4  3  3  4  1``
``````#  Ruby Program
#  Append the elements of queue in mirror-inverse order

#  Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :key, :left, :right

def initialize(key)
#  Set node value
self.key = key
self.left = nil
self.right = nil
end

end

#  Queue Node
class QNode
# Define the accessor and reader of class QNode
attr_accessor :key, :next

def initialize(key)
self.key = key
self.next = nil
end

end

# Define custom queue class
class MyQueue
# Define the accessor and reader of class MyQueue
attr_accessor :front, :rear, :size

def initialize()
self.front = nil
self.rear = nil
self.size = 0
end

#  Add a new node at last of queue
def enqueue(n)
node = QNode.new(n)
if (self.front == nil)
#  When first node of queue
self.front = node
else
#  Add node at last position
self.rear.next = node
end

self.size += 1
self.rear = node
end

#  Delete front node of queue
def dequeue()
if (self.front != nil)
if (self.rear == self.front)
self.rear = nil
self.front = nil
else
self.front = self.front.next
end

self.size -= 1
end

end

def isSize()
return self.size
end

def peek()
if (self.isSize() == 0)
return -1
else
return self.front.key
end

end

end

class Reflection
#   Mirror-Inverse insertion at the end of queue
def mirrorInverse(q, node)
if (node == nil)
return
end

#  Recursive approach to visit queue element
self.mirrorInverse(q, node.next)
#  Append element at the end
q.enqueue(node.key)
end

#  Display elements of queue
def display(q)
auxiliary = q.front
#  iterate the queue element
while (auxiliary != nil)
#  Display queue element
print(" ", auxiliary.key)
#  Visit to next node
auxiliary = auxiliary.next
end

print("\n")
end

end

def main()
q = MyQueue.new()
q.enqueue(1)
q.enqueue(4)
q.enqueue(3)
end

main()``````

#### Output

`````` 1 4 3 3 4 1
``````
``````/*
Scala Program
Append the elements of queue in mirror-inverse order
*/
// Binary Tree node
class TreeNode(var key: Int , var left: TreeNode , var right: TreeNode)
{
def this(key: Int)
{
this(key, null, null);
}
}
// Queue Node
class QNode(var key: Int , var next: QNode)
{
def this(key: Int)
{
this(key, null);
}
}
//Define custom queue class
class MyQueue(var front: QNode , var rear: QNode , var size: Int)
{
def this()
{
this(null, null, 0);
}
// Add a new node at last of queue
def enqueue(n: Int): Unit = {
var node: QNode = new QNode(n);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last position
this.rear.next = node;
}
this.size += 1;
this.rear = node;
}
// Delete front node of queue
def dequeue(): Unit = {
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
this.size -= 1;
}
}
def isSize(): Int = {
return this.size;
}
def peek(): Int = {
if (this.isSize() == 0)
{
return -1;
}
else
{
return this.front.key;
}
}
}
class Reflection
{
//  Mirror-Inverse insertion at the end of queue
def mirrorInverse(q: MyQueue, node: QNode): Unit = {
if (node == null)
{
return;
}
// Recursive approach to visit queue element
this.mirrorInverse(q, node.next);
// Append element at the end
q.enqueue(node.key);
}
// Display elements of queue
def display(q: MyQueue): Unit = {
var auxiliary: QNode = q.front;
// iterate the queue element
while (auxiliary != null)
{
// Display queue element
print(" " + auxiliary.key);
// Visit to next node
auxiliary = auxiliary.next;
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Reflection = new Reflection();
var q: MyQueue = new MyQueue();
q.enqueue(1);
q.enqueue(4);
q.enqueue(3);
}
}``````

#### Output

`` 1 4 3 3 4 1``
``````/*
Swift 4 Program
Append the elements of queue in mirror-inverse order
*/
// Binary Tree node
class TreeNode
{
var key: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ key: Int)
{
// Set node value
self.key = key;
self.left = nil;
self.right = nil;
}
}
// Queue Node
class QNode
{
var key: Int;
var next: QNode? ;
init(_ key: Int)
{
self.key = key;
self.next = nil;
}
}
//Define custom queue class
class MyQueue
{
var front: QNode? ;
var rear: QNode? ;
var size: Int;
init()
{
self.front = nil;
self.rear = nil;
self.size = 0;
}
// Add a new node at last of queue
func enqueue(_ n: Int)
{
let node: QNode? = QNode(n);
if (self.front == nil)
{
// When first node of queue
self.front = node;
}
else
{
// Add node at last position
self.rear!.next = node;
}
self.size += 1;
self.rear = node;
}
// Delete front node of queue
func dequeue()
{
if (self.front  != nil)
{
if (self.rear === self.front)
{
self.rear = nil;
self.front = nil;
}
else
{
self.front = self.front!.next;
}
self.size -= 1;
}
}
func isSize()->Int
{
return self.size;
}
func peek()->Int
{
if (self.isSize() == 0)
{
return -1;
}
else
{
return self.front!.key;
}
}
}
class Reflection
{
//  Mirror-Inverse insertion at the end of queue
func mirrorInverse(_ q: MyQueue, _ node: QNode? )
{
if (node == nil)
{
return;
}
// Recursive approach to visit queue element
self.mirrorInverse(q, node!.next);
// Append element at the end
q.enqueue(node!.key);
}
// Display elements of queue
func display(_ q: MyQueue? )
{
var auxiliary: QNode? = q!.front;
// iterate the queue element
while (auxiliary  != nil)
{
// Display queue element
print(" ", auxiliary!.key, terminator: "");
// Visit to next node
auxiliary = auxiliary!.next;
}
print(terminator: "\n");
}
}
func main()
{
let q: MyQueue = MyQueue();
q.enqueue(1);
q.enqueue(4);
q.enqueue(3);
}
main();``````

#### Output

``  1  4  3  3  4  1``
``````/*
Kotlin Program
Append the elements of queue in mirror-inverse order
*/
// Binary Tree node
class TreeNode
{
var key: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(key: Int)
{
// Set node value
this.key = key;
this.left = null;
this.right = null;
}
}
// Queue Node
class QNode
{
var key: Int;
var next: QNode ? ;
constructor(key: Int)
{
this.key = key;
this.next = null;
}
}
//Define custom queue class
class MyQueue
{
var front: QNode ? ;
var rear: QNode ? ;
var size: Int;
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a new node at last of queue
fun enqueue(n: Int): Unit
{
var node: QNode ? = QNode(n);
if (this.front == null)
{
// When first node of queue
this.front = node;
}
else
{
// Add node at last position
this.rear?.next = node;
}
this.size += 1;
this.rear = node;
}
// Delete front node of queue
fun dequeue(): Unit
{
if (this.front != null)
{
if (this.rear == this.front)
{
this.rear = null;
this.front = null;
}
else
{
this.front = this.front?.next;
}
this.size -= 1;
}
}
fun isSize(): Int
{
return this.size;
}
fun peek(): Int
{
if (this.isSize() == 0)
{
return -1;
}
else
{
return this.front!!.key;
}
}
}
class Reflection
{
//  Mirror-Inverse insertion at the end of queue
fun mirrorInverse(q: MyQueue , node : QNode ? ): Unit
{
if (node == null)
{
return;
}
// Recursive approach to visit queue element
this.mirrorInverse(q, node.next);
// Append element at the end
q.enqueue(node.key);
}
// Display elements of queue
fun display(q: MyQueue ): Unit
{
var auxiliary: QNode ? = q.front;
// iterate the queue element
while (auxiliary != null)
{
// Display queue element
print(" " + auxiliary.key);
// Visit to next node
auxiliary = auxiliary.next;
}
print("\n");
}
}
fun main(args: Array < String > ): Unit
{
var q: MyQueue = MyQueue();
q.enqueue(1);
q.enqueue(4);
q.enqueue(3);
}``````

#### Output

`` 1 4 3 3 4 1``

## Time Complexity

The time complexity of this approach is O(n), where n is the number of elements in the queue. This is because each element is visited once during the recursive traversal, and the enqueue operation takes constant time. The overall time complexity is linear in the number of elements in the queue.

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