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:
enQueue(int element)
: This operation adds an element to the back of the queue.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:
- enQueue(10)
- enQueue(11)
- enQueue(12)
- deQueue()
- enQueue(13)
- deQueue()
Initially, our queue is empty, and both our custom stacks are also empty.
- enQueue(10): After this operation, our queue should look like
[10]
. - enQueue(11): After this operation, our queue should look like
[10, 11]
. - enQueue(12): After this operation, our queue should look like
[10, 11, 12]
. - deQueue(): After this operation, our queue should look like
[11, 12]
, and the function should return10
. - enQueue(13): After this operation, our queue should look like
[11, 12, 13]
. - deQueue(): After this operation, our queue should look like
[12, 13]
, and the function should return11
.
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:
- Transfer all elements from stack
s
to stackauxiliary
. - Push the new element onto stack
s
. - Transfer all elements back from stack
auxiliary
to stacks
.
For deQueue operation:
- 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
- We define a custom stack class
MyStack
to create our stack data structure. - The
MyStack
class contains thepush
,pop
,peek
, andisEmpty
methods. - We define a custom queue class
MyQueue
that usesMyStack
to implement the queue. - The
MyQueue
class contains two main methods:enQueue
anddeQueue
. - 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. - 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;
}
// Add stack element
stack->top = node;
stack->size++;
}
// return top element of stack
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();
// Add Queue Element
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--;
}
}
// return top element of stack
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();
// Add Queue Element
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--;
}
}
// return top element of stack
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();
// Add Queue Element
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--;
}
}
// return top element of stack
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();
// Add Queue Element
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--;
}
}
// return top element of stack
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();
// Add Queue Element
$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--;
}
}
// return top element of stack
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();
// Add Queue Element
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
# return top element of stack
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()
# Add Queue Element
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_reader :element, :next
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_reader :top, :size
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
# return top element of stack
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_reader :s
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()
# Add Queue Element
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;
}
}
// return top element of stack
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();
// Add Queue Element
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;
}
}
// return top element of stack
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();
// Add Queue Element
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;
}
}
// return top element of stack
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();
// Add Queue Element
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
- The
enQueue
operation takes O(N) time, where N is the number of elements in the queue, because it involves transferring all elements from stacks
to the auxiliary stack and back. - 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).
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