Posted on by Kalkicode
Code Queue

Implement queue using stack

The problem is to implement a queue data structure using single stacks. A queue follows the First-In-First-Out (FIFO) principle, while a stack follows the Last-In-First-Out (LIFO) principle. We need to design a custom queue class that uses one custom stack classes to achieve the queue behavior.

Problem Statement

We need to create a custom queue class, `MyQueue`, with two main operations:

1. `enQueue(int element)`: This operation adds an element to the back of the queue.
2. `deQueue()`: This operation removes and returns the front element of the queue.

We must implement these operations efficiently using one custom stack classes: `MyStack` for the queue implementation.

Explanation with Example

Let's take an example to better understand the problem and its solution. Suppose we have a series of operations:

1. enQueue(10)
2. enQueue(11)
3. enQueue(12)
4. deQueue()
5. enQueue(13)
6. deQueue()

Initially, our queue is empty, and both our custom stacks are also empty.

1. enQueue(10): After this operation, our queue should look like `[10]`.
2. enQueue(11): After this operation, our queue should look like `[10, 11]`.
3. enQueue(12): After this operation, our queue should look like `[10, 11, 12]`.
4. deQueue(): After this operation, our queue should look like `[11, 12]`, and the function should return `10`.
5. enQueue(13): After this operation, our queue should look like `[11, 12, 13]`.
6. deQueue(): After this operation, our queue should look like `[12, 13]`, and the function should return `11`.

Idea to Solve the Problem

To implement a queue using one stacks, we use one stack (`s`) to represent the actual queue, and the other stack (`auxiliary`) is used to temporarily hold elements during enqueue operations.

For enQueue operation:

1. Transfer all elements from stack `s` to stack `auxiliary`.
2. Push the new element onto stack `s`.
3. Transfer all elements back from stack `auxiliary` to stack `s`.

For deQueue operation:

1. Simply pop the top element from stack `s` and return it as the front element of the queue.

Pseudocode

``````Class MyQueue:
Data:
s: MyStack (Main stack representing the queue)
Method:
enQueue(element):
auxiliary = MyStack()
while s is not empty:
auxiliary.push(s.peek())
s.pop()
s.push(element)
while auxiliary is not empty:
s.push(auxiliary.peek())
auxiliary.pop()

deQueue():
if s is not empty:
data = s.peek()
s.pop()
return data
else:
print "Empty Queue"
return -1``````

Algorithm Explanation

1. We define a custom stack class `MyStack` to create our stack data structure.
2. The `MyStack` class contains the `push`, `pop`, `peek`, and `isEmpty` methods.
3. We define a custom queue class `MyQueue` that uses `MyStack` to implement the queue.
4. The `MyQueue` class contains two main methods: `enQueue` and `deQueue`.
5. The `enQueue` method uses the auxiliary stack to reverse the order of elements in the main stack, allowing us to add the new element to the back of the queue.
6. The `deQueue` method simply removes and returns the front element from the main stack, simulating the dequeue operation of a queue.

Code Solution

``````// C Program for
// Implement queue using stack
#include <stdio.h>
#include <stdlib.h>

// Define stack node
struct StackNode
{
int element;
struct StackNode *next;
};
// Define a custom stack
struct MyStack
{
struct StackNode *top;
int size;
};
// Define a custom queue
struct MyQueue
{
struct MyStack *s;
};
struct MyStack *newStack()
{
//Make a stack
struct MyStack *stack = (struct MyStack *) malloc(sizeof(struct MyStack));
if (stack != NULL)
{
//Set node values
stack->top = NULL;
stack->size = 0;
}
else
{
printf("\nMemory overflow when create new stack\n");
}
return stack;
}
// Returns the status of empty or non empty stacks
int isEmpty(struct MyStack *stack)
{
if (stack->size > 0 && stack->top != NULL)
{
return 0;
}
else
{
return 1;
}
}
// Add node at the top of stack
void push(struct MyStack *stack, int element)
{
// Make a new node
struct StackNode *node = (struct StackNode *) malloc(sizeof(struct StackNode));
if (node == NULL)
{
printf("\nMemory overflow when create new stack Node \n");
}
else
{
node->element = element;
node->next = stack->top;
}
stack->top = node;
stack->size++;
}
int peek(struct MyStack *stack)
{
return stack->top->element;
}
// Remove top element of stack
void pop(struct MyStack *stack)
{
if (isEmpty(stack) == 0)
{
struct StackNode *temp = stack->top;
// Change top element of stack
stack->top = temp->next;
// remove previous top
free(temp);
temp = NULL;
stack->size--;
}
}
// Create new Queue
struct MyQueue *newQueue()
{
// Make a new queue
struct MyQueue *queue = (struct MyQueue *) malloc(sizeof(struct MyQueue));
if (queue != NULL)
{
queue->s = newStack();
}
else
{
printf("\nMemory overflow when create new queue\n");
}
return queue;
}
// Handles the request of add a queue element
void enQueue(struct MyQueue *queue, int data)
{
struct MyStack *auxiliary = newStack();
// Get all elements into auxiliary stack
while (isEmpty(queue->s) == 0)
{
push(auxiliary, peek(queue->s));
pop(queue->s);
}
// Add new element into empty stack
push(queue->s, data);
// Add auxiliary stack elements into actual stack of queue
while (isEmpty(auxiliary) == 0)
{
push(queue->s, peek(auxiliary));
pop(auxiliary);
}
}
// Handles the request of remove a queue element
int deQueue(struct MyQueue *queue)
{
if (isEmpty(queue->s) == 0)
{
int data = peek(queue->s);
// Remove top of stack
pop(queue->s);
return data;
}
printf("\n Empty Queue");
return -1;
}
int main()
{
struct MyQueue *queue = newQueue();
enQueue(queue, 10);
enQueue(queue, 11);
enQueue(queue, 12);
enQueue(queue, 13);
enQueue(queue, 14);
// Remove queue element
printf("\n %d", deQueue(queue));
printf("\n %d", deQueue(queue));
printf("\n %d", deQueue(queue));
printf("\n %d", deQueue(queue));
return 0;
}``````

Output

`````` 10
11
12
13``````
``````/*
Java program
Implement queue using stack
*/
// Define stack node
class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode top)
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
public int peek()
{
if (this.top == null)
{
return -1;
}
return this.top.element;
}
}
// Define custom queue class
class MyQueue
{
public MyStack s;
public MyQueue()
{
this.s = new MyStack();
}
//Add a new node at last of queue
public void enQueue(int element)
{
MyStack auxiliary = new MyStack();
// Get all elements into auxiliary stack
while (this.s.isEmpty() == false)
{
auxiliary.push(this.s.peek());
this.s.pop();
}
// Add new element into empty stack
this.s.push(element);
// Add auxiliary stack elements into actual stack of queue
while (auxiliary.isEmpty() == false)
{
this.s.push(auxiliary.peek());
auxiliary.pop();
}
}
//Delete first node of queue
public int deQueue()
{
if (this.s.isEmpty() == false)
{
int data = this.s.peek();
// Remove top of stack
this.s.pop();
return data;
}
System.out.print("\n Empty Queue");
return -1;
}
}
public class QueueUsingStack
{
public static void main(String[] args)
{
MyQueue queue = new MyQueue();
queue.enQueue(10);
queue.enQueue(11);
queue.enQueue(12);
queue.enQueue(13);
queue.enQueue(14);
// Remove queue element
System.out.print("\n " + queue.deQueue());
System.out.print("\n " + queue.deQueue());
System.out.print("\n " + queue.deQueue());
System.out.print("\n " + queue.deQueue());
}
}``````

Output

`````` 10
11
12
13``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ program
Implement queue using stack
*/

// Define stack node
class StackNode
{
public: int element;
StackNode *next;
StackNode(int element, StackNode *top)
{
this->element = element;
this->next = top;
}
};
// Define a custom stack
class MyStack
{
public: StackNode *top;
int size;
MyStack()
{
//Set node values
this->top = NULL;
this->size = 0;
}
// Add node at the top of stack
void push(int element)
{
this->top = new StackNode(element, this->top);
this->size++;
}
bool isEmpty()
{
if (this->size > 0 && this->top != NULL)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
void pop()
{
if (this->size > 0 && this->top != NULL)
{
StackNode *temp = this->top;
// Change top element of stack
this->top = temp->next;
// remove previous top
delete temp;
temp = NULL;
this->size--;
}
}
int peek()
{
if (this->top == NULL)
{
return -1;
}
return this->top->element;
}
};
// Define custom queue class
class MyQueue
{
public: MyStack *s;
MyQueue()
{
this->s = new MyStack();
}
//Add a new node at last of queue
void enQueue(int element)
{
MyStack auxiliary = MyStack();
// Get all elements into auxiliary stack
while (this->s->isEmpty() == false)
{
auxiliary.push(this->s->peek());
this->s->pop();
}
// Add new element into empty stack
this->s->push(element);
// Add auxiliary stack elements into actual stack of queue
while (auxiliary.isEmpty() == false)
{
this->s->push(auxiliary.peek());
auxiliary.pop();
}
}
//Delete first node of queue
int deQueue()
{
if (this->s->isEmpty() == false)
{
int data = this->s->peek();
// Remove top of stack
this->s->pop();
return data;
}
cout << "\n Empty Queue";
return -1;
}
};

int main()
{
MyQueue queue = MyQueue();
queue.enQueue(10);
queue.enQueue(11);
queue.enQueue(12);
queue.enQueue(13);
queue.enQueue(14);
// Remove queue element
cout << "\n " << queue.deQueue();
cout << "\n " << queue.deQueue();
cout << "\n " << queue.deQueue();
cout << "\n " << queue.deQueue();
return 0;
}``````

Output

`````` 10
11
12
13``````
``````// Include namespace system
using System;
/*
C# program
Implement queue using stack
*/
// Define stack node
public class StackNode
{
public int element;
public StackNode next;
public StackNode(int element, StackNode top)
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
public class MyStack
{
public StackNode top;
public int size;
public MyStack()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
public void push(int element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
public Boolean isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public void pop()
{
if (this.size > 0 && this.top != null)
{
StackNode temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
public int peek()
{
if (this.top == null)
{
return -1;
}
return this.top.element;
}
}
// Define custom queue class
public class MyQueue
{
public MyStack s;
public MyQueue()
{
this.s = new MyStack();
}
//Add a new node at last of queue
public void enQueue(int element)
{
MyStack auxiliary = new MyStack();
// Get all elements into auxiliary stack
while (this.s.isEmpty() == false)
{
auxiliary.push(this.s.peek());
this.s.pop();
}
// Add new element into empty stack
this.s.push(element);
// Add auxiliary stack elements into actual stack of queue
while (auxiliary.isEmpty() == false)
{
this.s.push(auxiliary.peek());
auxiliary.pop();
}
}
//Delete first node of queue
public int deQueue()
{
if (this.s.isEmpty() == false)
{
int data = this.s.peek();
// Remove top of stack
this.s.pop();
return data;
}
Console.Write("\n Empty Queue");
return -1;
}
}
public class QueueUsingStack
{
public static void Main(String[] args)
{
MyQueue queue = new MyQueue();
queue.enQueue(10);
queue.enQueue(11);
queue.enQueue(12);
queue.enQueue(13);
queue.enQueue(14);
// Remove queue element
Console.Write("\n " + queue.deQueue());
Console.Write("\n " + queue.deQueue());
Console.Write("\n " + queue.deQueue());
Console.Write("\n " + queue.deQueue());
}
}``````

Output

`````` 10
11
12
13``````
``````<?php
/*
Php program
Implement queue using stack
*/
// Define stack node
class StackNode
{
public \$element;
public \$next;

function __construct(\$element, \$top)
{
\$this->element = \$element;
\$this->next = \$top;
}
}
// Define a custom stack
class MyStack
{
public \$top;
public \$size;

function __construct()
{
//Set node values
\$this->top = null;
\$this->size = 0;
}
// Add node at the top of stack
public	function push(\$element)
{
\$this->top = new StackNode(\$element, \$this->top);
\$this->size++;
}
public	function isEmpty()
{
if (\$this->size > 0 && \$this->top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
public	function pop()
{
if (\$this->size > 0 && \$this->top != null)
{
\$temp = \$this->top;
// Change top element of stack
\$this->top = \$temp->next;
// remove previous top
\$temp = null;
\$this->size--;
}
}
public	function peek()
{
if (\$this->top == null)
{
return -1;
}
return \$this->top->element;
}
}
// Define custom queue class
class MyQueue
{
public \$s;

function __construct()
{
\$this->s = new MyStack();
}
//Add a new node at last of queue
public	function enQueue(\$element)
{
\$auxiliary = new MyStack();
// Get all elements into auxiliary stack
while (\$this->s->isEmpty() == false)
{
\$auxiliary->push(\$this->s->peek());
\$this->s->pop();
}
// Add new element into empty stack
\$this->s->push(\$element);
// Add auxiliary stack elements into actual stack of queue
while (\$auxiliary->isEmpty() == false)
{
\$this->s->push(\$auxiliary->peek());
\$auxiliary->pop();
}
}
//Delete first node of queue
public	function deQueue()
{
if (\$this->s->isEmpty() == false)
{
\$data = \$this->s->peek();
// Remove top of stack
\$this->s->pop();
return \$data;
}
echo "\n Empty Queue";
return -1;
}
}
function main()
{
\$queue = new MyQueue();
\$queue->enQueue(10);
\$queue->enQueue(11);
\$queue->enQueue(12);
\$queue->enQueue(13);
\$queue->enQueue(14);
// Remove queue element
echo "\n ". \$queue->deQueue();
echo "\n ". \$queue->deQueue();
echo "\n ". \$queue->deQueue();
echo "\n ". \$queue->deQueue();
}
main();``````

Output

`````` 10
11
12
13``````
``````/*
Node Js program
Implement queue using stack
*/
// Define stack node
class StackNode
{
constructor(element, top)
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
class MyStack
{
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
push(element)
{
this.top = new StackNode(element, this.top);
this.size++;
}
isEmpty()
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
pop()
{
if (this.size > 0 && this.top != null)
{
var temp = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size--;
}
}
peek()
{
if (this.top == null)
{
return -1;
}
return this.top.element;
}
}
// Define custom queue class
class MyQueue
{
constructor()
{
this.s = new MyStack();
}
//Add a new node at last of queue
enQueue(element)
{
var auxiliary = new MyStack();
// Get all elements into auxiliary stack
while (this.s.isEmpty() == false)
{
auxiliary.push(this.s.peek());
this.s.pop();
}
// Add new element into empty stack
this.s.push(element);
// Add auxiliary stack elements into actual stack of queue
while (auxiliary.isEmpty() == false)
{
this.s.push(auxiliary.peek());
auxiliary.pop();
}
}
//Delete first node of queue
deQueue()
{
if (this.s.isEmpty() == false)
{
var data = this.s.peek();
// Remove top of stack
this.s.pop();
return data;
}
process.stdout.write("\n Empty Queue");
return -1;
}
}
function main()
{
var queue = new MyQueue();
queue.enQueue(10);
queue.enQueue(11);
queue.enQueue(12);
queue.enQueue(13);
queue.enQueue(14);
// Remove queue element
process.stdout.write("\n " + queue.deQueue());
process.stdout.write("\n " + queue.deQueue());
process.stdout.write("\n " + queue.deQueue());
process.stdout.write("\n " + queue.deQueue());
}
main();``````

Output

`````` 10
11
12
13``````
``````#  Python 3 program
#  Implement queue using stack

#  Define stack node
class StackNode :

def __init__(self, element, top) :
self.element = element
self.next = top

#  Define a custom stack
class MyStack :

def __init__(self) :
# Set node values
self.top = None
self.size = 0

#  Add node at the top of stack
def push(self, element) :
self.top = StackNode(element, self.top)
self.size += 1

def isEmpty(self) :
if (self.size > 0 and self.top != None) :
return False
else :
return True

#  Remove top element of stack
def pop(self) :
if (self.size > 0 and self.top != None) :
temp = self.top
#  Change top element of stack
self.top = temp.next
#  remove previous top
temp = None
self.size -= 1

def peek(self) :
if (self.top == None) :
return -1

return self.top.element

#  Define custom queue class
class MyQueue :

def __init__(self) :
self.s = MyStack()

# Add a new node at last of queue
def enQueue(self, element) :
auxiliary = MyStack()
#  Get all elements into auxiliary stack
while (self.s.isEmpty() == False) :
auxiliary.push(self.s.peek())
self.s.pop()

#  Add new element into empty stack
self.s.push(element)
#  Add auxiliary stack elements into actual stack of queue
while (auxiliary.isEmpty() == False) :
self.s.push(auxiliary.peek())
auxiliary.pop()

# Delete first node of queue
def deQueue(self) :
if (self.s.isEmpty() == False) :
data = self.s.peek()
#  Remove top of stack
self.s.pop()
return data

print("\n Empty Queue", end = "")
return -1

def main() :
queue = MyQueue()
queue.enQueue(10)
queue.enQueue(11)
queue.enQueue(12)
queue.enQueue(13)
queue.enQueue(14)
#  Remove queue element
print("\n ", queue.deQueue(), end = "")
print("\n ", queue.deQueue(), end = "")
print("\n ", queue.deQueue(), end = "")
print("\n ", queue.deQueue(), end = "")

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

Output

``````  10
11
12
13``````
``````#  Ruby program
#  Implement queue using stack

#  Define stack node
class StackNode
# Define the accessor and reader of class StackNode
attr_accessor :element, :next

def initialize(element, top)
self.element = element
self.next = top
end

end

#  Define a custom stack
class MyStack
# Define the accessor and reader of class MyStack
attr_accessor :top, :size

def initialize()
# Set node values
self.top = nil
self.size = 0
end

#  Add node at the top of stack
def push(element)
self.top = StackNode.new(element, self.top)
self.size += 1
end

def isEmpty()
if (self.size > 0 && self.top != nil)
return false
else
return true
end

end

#  Remove top element of stack
def pop()
if (self.size > 0 && self.top != nil)
temp = self.top
#  Change top element of stack
self.top = temp.next
#  remove previous top
temp = nil
self.size -= 1
end

end

def peek()
if (self.top == nil)
return -1
end

return self.top.element
end

end

#  Define custom queue class
class MyQueue
# Define the accessor and reader of class MyQueue
attr_accessor :s

def initialize()
self.s = MyStack.new()
end

# Add a new node at last of queue
def enQueue(element)
auxiliary = MyStack.new()
#  Get all elements into auxiliary stack
while (self.s.isEmpty() == false)
auxiliary.push(self.s.peek())
self.s.pop()
end

#  Add new element into empty stack
self.s.push(element)
#  Add auxiliary stack elements into actual stack of queue
while (auxiliary.isEmpty() == false)
self.s.push(auxiliary.peek())
auxiliary.pop()
end

end

# Delete first node of queue
def deQueue()
if (self.s.isEmpty() == false)
data = self.s.peek()
#  Remove top of stack
self.s.pop()
return data
end

print("\n Empty Queue")
return -1
end

end

class QueueUsingStack end

def main()
queue = MyQueue.new()
queue.enQueue(10)
queue.enQueue(11)
queue.enQueue(12)
queue.enQueue(13)
queue.enQueue(14)
#  Remove queue element
print("\n ", queue.deQueue())
print("\n ", queue.deQueue())
print("\n ", queue.deQueue())
print("\n ", queue.deQueue())
end

main()``````

Output

`````` 10
11
12
13``````
``````/*
Scala program
Implement queue using stack
*/
// Define stack node
class StackNode(var element: Int , var next: StackNode);
// Define a custom stack
class MyStack(var top: StackNode , var size: Int)
{
def this()
{
this(null, 0);
}
// Add node at the top of stack
def push(element: Int): Unit = {
this.top = new StackNode(element, this.top);
this.size += 1;
}
def isEmpty(): Boolean = {
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
def pop(): Unit = {
if (this.size > 0 && this.top != null)
{
var temp: StackNode = this.top;
// Change top element of stack
this.top = temp.next;
// remove previous top
temp = null;
this.size -= 1;
}
}
def peek(): Int = {
if (this.top == null)
{
return -1;
}
return this.top.element;
}
}
// Define custom queue class
class MyQueue(var s: MyStack)
{
def this()
{
this(new MyStack());
}
//Add a new node at last of queue
def enQueue(element: Int): Unit = {
var auxiliary: MyStack = new MyStack();
// Get all elements into auxiliary stack
while (this.s.isEmpty() == false)
{
auxiliary.push(this.s.peek());
this.s.pop();
}
// Add new element into empty stack
this.s.push(element);
// Add auxiliary stack elements into actual stack of queue
while (auxiliary.isEmpty() == false)
{
this.s.push(auxiliary.peek());
auxiliary.pop();
}
}
//Delete first node of queue
def deQueue(): Int = {
if (this.s.isEmpty() == false)
{
var data: Int = this.s.peek();
// Remove top of stack
this.s.pop();
return data;
}
print("\n Empty Queue");
return -1;
}
}

object Main
{
def main(args: Array[String]): Unit = {
var queue: MyQueue = new MyQueue();
queue.enQueue(10);
queue.enQueue(11);
queue.enQueue(12);
queue.enQueue(13);
queue.enQueue(14);
// Remove queue element
print("\n " + queue.deQueue());
print("\n " + queue.deQueue());
print("\n " + queue.deQueue());
print("\n " + queue.deQueue());
}
}``````

Output

`````` 10
11
12
13``````
``````/*
Swift 4 program
Implement queue using stack
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode? ;
init(_ element: Int, _ top: StackNode? )
{
self.element = element;
self.next = top;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode? ;
var size: Int;
init()
{
//Set node values
self.top = nil;
self.size = 0;
}
// Add node at the top of stack
func push(_ element: Int)
{
self.top = StackNode(element, self.top);
self.size += 1;
}
func isEmpty()->Bool
{
if (self.size > 0 && self.top  != nil)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
func pop()
{
if (self.size > 0 && self.top  != nil)
{
var temp: StackNode? = self.top;
// Change top element of stack
self.top = temp!.next;
// remove previous top
temp = nil;
self.size -= 1;
}
}
func peek()->Int
{
if (self.top == nil)
{
return -1;
}
return self.top!.element;
}
}
// Define custom queue class
class MyQueue
{
var s: MyStack;
init()
{
self.s = MyStack();
}
//Add a new node at last of queue
func enQueue(_ element: Int)
{
let auxiliary: MyStack = MyStack();
// Get all elements into auxiliary stack
while (self.s.isEmpty() == false)
{
auxiliary.push(self.s.peek());
self.s.pop();
}
// Add new element into empty stack
self.s.push(element);
// Add auxiliary stack elements into actual stack of queue
while (auxiliary.isEmpty() == false)
{
self.s.push(auxiliary.peek());
auxiliary.pop();
}
}
//Delete first node of queue
func deQueue()->Int
{
if (self.s.isEmpty() == false)
{
let data: Int = self.s.peek();
// Remove top of stack
self.s.pop();
return data;
}
print("\n Empty Queue", terminator: "");
return -1;
}
}
class QueueUsingStack
{}
func main()
{
let queue: MyQueue = MyQueue();
queue.enQueue(10);
queue.enQueue(11);
queue.enQueue(12);
queue.enQueue(13);
queue.enQueue(14);
// Remove queue element
print("\n ", queue.deQueue(), terminator: "");
print("\n ", queue.deQueue(), terminator: "");
print("\n ", queue.deQueue(), terminator: "");
print("\n ", queue.deQueue(), terminator: "");
}
main();``````

Output

``````  10
11
12
13``````
``````/*
Kotlin program
Implement queue using stack
*/
// Define stack node
class StackNode
{
var element: Int;
var next: StackNode ? ;
constructor(element: Int, top: StackNode ? )
{
this.element = element;
this.next = top;
}
}
// Define a custom stack
class MyStack
{
var top: StackNode ? ;
var size: Int;
constructor()
{
//Set node values
this.top = null;
this.size = 0;
}
// Add node at the top of stack
fun push(element: Int): Unit
{
this.top = StackNode(element, this.top);
this.size += 1;
}
fun isEmpty(): Boolean
{
if (this.size > 0 && this.top != null)
{
return false;
}
else
{
return true;
}
}
// Remove top element of stack
fun pop(): Unit
{
if (this.size > 0 && this.top != null)
{
var temp: StackNode ? = this.top;
// Change top element of stack
this.top = temp?.next;

this.size -= 1;
}
}
fun peek(): Int
{
if (this.top == null)
{
return -1;
}
return this.top!!.element;
}
}
// Define custom queue class
class MyQueue
{
var s: MyStack;
constructor()
{
this.s = MyStack();
}
//Add a new node at last of queue
fun enQueue(element: Int): Unit
{
var auxiliary: MyStack = MyStack();
// Get all elements into auxiliary stack
while (this.s.isEmpty() == false)
{
auxiliary.push(this.s.peek());
this.s.pop();
}
// Add new element into empty stack
this.s.push(element);
// Add auxiliary stack elements into actual stack of queue
while (auxiliary.isEmpty() == false)
{
this.s.push(auxiliary.peek());
auxiliary.pop();
}
}
//Delete first node of queue
fun deQueue(): Int
{
if (this.s.isEmpty() == false)
{
var data: Int = this.s.peek();
// Remove top of stack
this.s.pop();
return data;
}
print("\n Empty Queue");
return -1;
}
}
fun main(args: Array < String > ): Unit
{
var queue: MyQueue = MyQueue();
queue.enQueue(10);
queue.enQueue(11);
queue.enQueue(12);
queue.enQueue(13);
queue.enQueue(14);
// Remove queue element
print("\n " + queue.deQueue());
print("\n " + queue.deQueue());
print("\n " + queue.deQueue());
print("\n " + queue.deQueue());
}``````

Output

`````` 10
11
12
13``````

Resultant Output Explanation

The output provided in the example is:

``````10
11
12
13``````

This output corresponds to the elements removed from the queue using the `deQueue` method in the order they were inserted using the `enQueue` method. This demonstrates the FIFO behavior of the queue data structure.

Time Complexity

1. The `enQueue` operation takes O(N) time, where N is the number of elements in the queue, because it involves transferring all elements from stack `s` to the auxiliary stack and back.
2. The `deQueue` operation takes O(1) time, as it simply pops the top element from the main stack.

Overall, the amortized time complexity for both `enQueue` and `deQueue` operations is O(1).

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