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;
	}
	// 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

  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.

New Comment





Categories
Relative Post