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 Array. Here we are going to create an array which dynamically grows by twice its size.
Here we have got some frequently used methods. Now here we go ...
enqueue(): Pushes data into the queue.
dequeue(): Removes data from the queue.
length(): This method returns integer value as the no of elements of the queue.
Other method implementation can be structured such as isEmpty(), front(), 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 an Array with 5 as its size. We define a variable as rear and front and this variable gets initialized by -1 and when we enqueue element into the queue we place this value at the 0th location so before inserting element into the queue we increment the rear variable by one the rear becomes 0 and we place the value into queue and same process goes on till the queue is full.
Once queue is full we have to do a process to increase the size of queue and we can achieve by creating an array with double the size of the array and we copy queue elements into the newly created array so once again we have got enough space in new array. We can do the implementation by incrementing its size by fixed size such as 5 rather than doubling the size of the array. Doubling the size will take more space but incrementing the size of array by fixed number will take more time as we may need to copy it more frequently. Now which implementation you choose will be based on your requirement, if you have enough resources (memory) then we have to go with the bigger size array.
We need care while enqueue the element in the queue. Enqueue process the divided in two parts first is the first time when we insert element in the queue we need to pay attention while inserting first element. At that point of time we need to increment rear as well as front so that front variable will always give me the first element of the queue.
Challenges:
- We may have got Queue Full Exception, if we have not implemented dynamic incrementation. As we have got an Array which grows as per need, we will never face Queue Full 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.
- There may be a situation where rear variable will point to last index of the array and front variable will point to the second last index of the array then we need to apply some logic so that index will be changed and waste memory will not occur.
- When we apply above logic we solve other problem of queue which gets solved using Circular Queue concept. Here we have achieved circular queue implementation as well.
/* Class definition to implement Queue using Array */
package com.ds.queue;
public class QueueArray
{
Integer[] queue;
Integer rear;
Integer front;
public QueueArray() {
queue = new Integer[5];
rear = front = -1;
}
public void enqueue(int value)
{
int arrLen = queue.length;
if (front < 0) {
queue[0] = value;
rear = front = 0;
} else {
rear++;
rear = rear % arrLen;
if (rear == front) {
copyArray(arrLen);
arrLen = arrLen * 2;
} else {
if (queue[rear] == null) {
queue[rear] = value;
}
}
}
}
public void copyArray(int len)
{
Integer[] dummyQueue = new Integer[len * 2];
int tmpFront = front;
int newArrPoint = 0;
for (int i = tmpFront; i < len; i++) {
dummyQueue[newArrPoint] = queue[tmpFront % len];
newArrPoint++;
tmpFront++;
}
tmpFront = front;
for (int i = 0; i < tmpFront; i++) {
dummyQueue[newArrPoint] = queue[i];
newArrPoint++;
}
queue = dummyQueue;
front = 0;
rear = newArrPoint - 1;
}
public int length()
{
int queueLen = 0;
for (int i = front; i <= rear; i++) {
queueLen++;
}
return queueLen;
}
public void dequeue()
{
queue[front] = null;
front++;
}
public void printQueue()
{
int arrLen = queue.length;
int tmpFront = front;
String printString = "";
for (int i = 0; i < arrLen; i++) {
Integer arrayVal = queue[tmpFront % arrLen];
if (arrayVal == null) {
break;
}
printString += arrayVal.toString() + " --> ";
tmpFront++;
}
if ("".equals(printString)) {
System.out.println("Queue is empty");
} else {
System.out.println(printString);
}
}
public static void main(String[] args) throws Exception
{
QueueArray queue = new QueueArray();
queue.enqueue(4);
queue.enqueue(2);
queue.enqueue(1);
queue.enqueue(4);
queue.enqueue(7);
/**
* if enqueue next element then need to
* increase size of the array
**/
* if enqueue next element then need to
* increase size of the array
**/
queue.dequeue();
queue.dequeue();
queue.enqueue(9);
queue.enqueue(0);
queue.enqueue(3);
queue.enqueue(2);
queue.enqueue(1);
queue.enqueue(9);
queue.dequeue();
queue.dequeue();
queue.enqueue(10);
queue.printQueue();
System.out.println("queue length is "+queue.length());
}
}
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