Background:
As we know array is used to store data in sequential manner in memory. Here accessing of elements is based on array index. But in case of queue, accessing of elements is not based on index it is based on type of operation as given below.
1. Addition of element - It always happens on head/front end of the queue.
2. Processing or removal of element - It always happens on rear/back/tail end of the queue.
So to implement queue using array we need a wrapper class around the array which will implement queue operations using array as storage medium.
Strategy
We need following instance variables and methods in wrapper class QueueUsingArray to implement queue.
1. front/head pointer - It will always point to the front of the queue or the last inserted element in the queue.
2. rear/back/tail- It will point to the element which will be next processed or removed from the queue for processing.
3. size - Since array is a static data type so it is required to have size variable of array to check overflow condition of the queue.
4. enQueue() - This operation will add elements in the array fulfilling all constraints of the queue.
4. deQueue() - This operation will fetch and remove an element from the queue pointed by the rear pointer fulfilling all the constraints of the queue.
5. peek() - This operation will fetch an element from the queue pointed by front pointer fulfilling all the constraints of the queue.
6. rear() - This operation will fetch an element from the queue pointed by rear pointer fulfilling all the constraints of the queue.
7. getSize() - It will return number of elements present in the queue.
8. isEmpty() - It will return true if the queue is empty otherwise false.
9. isFull()- It will return true if the queue is full otherwise false.
10. storage - This is the array which will store all the elements of the queue.
Below is the class diagram for the implementation of the queue mentioned above:
Here we are going to write algorithm for all operations of the queue mentioned in the above diagram.
enQueue( item )- Below is the algorithm for push() operation.
enQueue(item)
{
1. if (head< size-1)
2. if(rear==-1)
3. rear++
4. head++
5. storage[head]=item
6. else
7. throw exception "Queue overflow"
}
deQueue( item )- This operation is performed on the element pointed by the rear pointer. Once we remove the item from the queue the place in the array is vacant with no use. So to use that vacant place it is necessary to shift other following elements towards rear pointer. Due to shifting of the elements time complexity of this operation is O(n). Below figure demonstrates the same:
Based on the above explanation, two cases are possible.
1. If head=rear==0 then it means queue has just one element. In this case we have to decrement both of the pointers.
2. If head>0 then decrement head pointer and shift remaining elements towards the rear pointer.
Below is the implementation of deQueue() algorithm:
deQueue():item
{
1. if (rear==-1)
2. throw exception "Stack is Empty"
3. result=null
5. if(head==0)
6. return storage[rear]
7. head--
8. rear--
9. else
10. result=storage[rear]
11. for i=rear+1 to i=head
12. storage[i-1]=storage[i]
13. head--
14. return result
}
peek()- It returns the item pointed by the head pointer.
peek():item
{
1. if (head==-1)
2. throw exception "Queue is Empty"
3. else
5. return storage[head]
}
rear()- It returns the item pointed by the rear pointer.
rear():item
{
1. if (rear==-1)
2. throw exception "Queue is Empty"
3. else
5. return storage[rear]
}
getSize() - Using the head pointer size of the queue is also known because the head pointer always points to the index of last inserted element and based on the above mentioned definition of deQueue() operation rear pointer is fixed on index 0. So size of the queue=head+1. Below is the implementation of getSize() method.
getSize()
{
return head+1;
}
isEmpty() - Below is the implementation of isEmpty() method.
isEmpty()
{
return head==-1;
}
isFull()- Below is the implementation of isFull() method.
isFull()
{
return head==size-1;
}
Below is the java code implementation of the above discussed algorithms
public class QueueUsingArrayTest {
/**
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
QueueUsingArray<String> strQueue=new QueueUsingArray<String>(5);
strQueue.enQueue("Ram");
strQueue.enQueue("Shyam");
strQueue.enQueue("Meena");
strQueue.enQueue("Alfred");
System.out.println("Queue size="+strQueue.getSize());
System.out.println("is Queue empty="+strQueue.isEmpty());
System.out.println("============================================");
System.out.println("Peek element is="+strQueue.peek());
System.out.println("Rear element is="+strQueue.rear());
System.out.println("1st dequeued element is="+strQueue.deQueue());
System.out.println("2nd dequeued element is="+strQueue.deQueue());
System.out.println("3rd dequeued element is="+strQueue.deQueue());
System.out.println("Queue size="+strQueue.getSize());
System.out.println("is Queue empty="+strQueue.isEmpty());
System.out.println("4th dequeued element is="+strQueue.deQueue());
System.out.println("is Queue empty="+strQueue.isEmpty());
}
}
class QueueUsingArray<T>
{
private int size;
private int head;
private int rear;
private T[] storage;
public QueueUsingArray(int size)
{
this.size=size;
storage=(T[]) new Object[size];
head=-1;
rear=-1;
}
public boolean enQueue(T item) throws Exception
{
if(head<size-1)
{
if(rear==-1)
{
rear++;
}
head++;
storage[head]=item;
}
else
{
throw new Exception("Queue Overflow");
}
return true;
}
public T deQueue() throws Exception
{
T item;
if(rear==-1)
{
throw new Exception("Queue Underflow");
}
item= storage[rear];
if(head==0)
{
head--;
rear--;
return item;
}
for (int i = rear+1; i <= head; i++) {
storage[i-1]=storage[i];
}
head--;
return item;
}
public T peek() throws Exception
{
T item;
if(head>=0)
{
item= storage[head];
}
else
{
throw new Exception("Queue Underflow");
}
return item;
}
public T rear() throws Exception
{
T item;
if(rear>=0)
{
item= storage[rear];
}
else
{
throw new Exception("Queue Underflow");
}
return item;
}
public int getSize()
{
return head+1;
}
public boolean isEmpty()
{
return head==-1;
}
public boolean isFull()
{
return head==size-1;
}
}
