Queue: Queue is the data structure which works on the concept of FIFO (First In First Out). Consider one real time example of queue ... lets assume there is a queue at the box office and we are in the queue to get ticket of movie Interstellar, now if i enter in the queue before you then i will get ticket and move out of the queue and you will follow me as you have entered the queue after me. Queue data structure can be implemented with two ideas one using Array and another using Link List. Now lets discuss concept of Queue implementation using Link List. Implementation using link list will have an edge over Array implementation, we don't need to worry about the size of the queue as far as we have memory available in the machine we can create node to enqueue the element. You will never face Queue Full Exception.
Here we have got some frequently used methods. Now here we go ...
enqueue(): Pushes data into the queue.
dequeue(): Removes data from the queue.
top(): This method returns first element of the queue.
Other method implementation can be structured such as isEmpty(), length(), etc. Once you understand the concept of queue in java or any language you will be able to design you own implementation of all the problems we may need for queue.
Implementation:
We have got a class called Node which act as a memory box which contains value and address of the next node. Once a node is created for the first time that node is being referred as Head Node and this node will be node till it gets deleted by other method. when other node is being created and ready to push further and head node keeps address of its node. This process goes on till we want to stop enqueue process. Please check the code. Same process need to be addressed for dequeue method. Last but not the least length, to find the no. of node in the list we need to iterate through the list till next node becomes null and counter variable will store the each iteration count. For getting first node we don't need to iterate as we have front node to keep track as dequeue happens from front not from rear.
We need to be more careful while dequeue operation as we need to change the location of front node, because dequeue happens from the front and once front node gets deleted the we need to move front to the next element.
Challenges:
- We will never get Queue Full Exception as node is getting created at run time and there is no size specification available. So there is no chance to get this exception.
- We will get another type of Exception, i.e. Queue Empty Exception, if we get dequeue() method call again and again. Once the queue is empty i.e no more element to remove then we can display Queue Empty Exception.
/* Class definition to implement Queue using Link List */
package com.ds.queue;
import com.ds.common.Node;
public class QueueList
{
Node rear;
Node front;
public QueueList() {
rear = front = null;
}
public Node add(int val, Node head)
{
Node tmpNode = head;
if (head == null) {
tmpNode = head = new Node(val);
} else {
while (tmpNode.next != null) {
tmpNode = tmpNode.next;
}
tmpNode.next = new Node(val);
}
return head;
}
{
rear = add(value, rear);
if (front == null) {
front = rear;
}
}
public void dequeue() throws Exception
{
if (front != null) {
front = front.next;
} else {
System.out.println("Queue is empty");
}
}
public void top() throws Exception
{
if (front != null) {
System.out.println("Top element is " + front.data);
} else {
System.out.println("Queue is empty");
}
}
/**
* Prints all the nodes value in the list
*/
public void print() throws Exception
{
if (front != null) {
Node tmpNode = head;
while (tmpNode != null) {
System.out.print(tmpNode.data + " -> ");
tmpNode = tmpNode.next;
}
System.out.println("");
} else {System.out.println("Queue is empty");
}
}
public static void main(String[] args) throws Exception
{
QueueList queue = new QueueList();
/** Input can be taken from user directly using
* scanner class Please check with Quick Sort
* implementation for reference
**/
queue.enqueue(2);
queue.enqueue(6);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(9);
queue.enqueue(1);
queue.print();
queue.dequeue();
queue.dequeue();
queue.dequeue();
queue.print();
queue.top();
}
}
// Node class needs to be created separately
// Node Class specification is below
package com.ds.common;
public class Node
{
public Integer data;
public Node next;
public Node(int val)
{
data = val;
next = null;
}
}
Comparison: We got to compare both the implementation i.e. Array implementation and Link List implementation. Lets discuss both the implementation then you will be in better position to decide which implementation is better.
Array: Array implementation takes constant time for enqueue(), dequeue(), top(), length() as we have got top variable which gives us the exact location of the element for dequeue(), enqueue() and other described methods. The only problem with this concept is when we have to use dynamic array we need n time to copy the elements in new array which has been created to eliminate Queue Full Exception.
If we have the scenario where the total no of element count is fixed then array implementation of queue is preferable over Link List implementation of Queue.
Link List: Link list implementation need n time for every enqueue(), dequeue() and other operation as we need to iterate form the first node to the last node where element needs to be enqueue(), dequeue() or other operations. So here we have got the idea of both the concepts and based on the scenario we need to use for better performance.
No comments:
Post a Comment