It is an ordered list of elements n in which all deletions are made at one end called the front end and all insertions at the other end called the rear end . In other way you can say Queue follow the FIFO rule to access the data items.
Example :
1. PRACTICAL EXAMPLE : A line at a ticket counter for buying tickets operates on above rules
2. IN COMPUTER WORLD : In a batch processing system, jobs are queued up for processing.
Primary operations defined on a Queue:
EnQueue : This is used to add elements into the queue at the back end.
DeQueue : This is used to delete elements from a queue from the front end.
Also "IsEmpty()" and "IsFull()" can be defined to test whether the queue is Empty or full.
Example :
1. PRACTICAL EXAMPLE : A line at a ticket counter for buying tickets operates on above rules
2. IN COMPUTER WORLD : In a batch processing system, jobs are queued up for processing.
Primary operations defined on a Queue:
EnQueue : This is used to add elements into the queue at the back end.
DeQueue : This is used to delete elements from a queue from the front end.
Also "IsEmpty()" and "IsFull()" can be defined to test whether the queue is Empty or full.
Suppose Queue has maximum capacity is of 40 element but at the present there are only 4 element in the queue. Then our queue will be like as follows:
When an element is deleted from queue the front is increased by 1 i.e front =front+1 and similarly when an element is added in queue the rear is increased by 1 i.e. rear=rear+1.
Suppose in above example if we delete 11 then the front will point to 2 . see the following figure .
Algorithm for the addition of element in a Queue:
add(item, queue,n ,rear)
{
if(rear==n)
print " queue is full"
else
{
rear=rear+1;
queue[rear]=item;
}
}
Algorithm for the deletion of element in a Queue:
delete(item,queue,rear,front)
{
if(rear==front )
print "queue is empty "
else
{
item=queue[front];
fornt=front+1;
}
}
Note : See the condition rear == front . When front==rear it means queue is empty.
Example to illustrate the addition and deletion in a queue
See the below rule very carefully :
1. Initially rear and front both are 0.
2. When the first element is added in the queue ,both front and rear are increased by 1.
3. But after the first element . Rear will be increased by 1 only when an element is added and front will be increased 1 only after an element is deleted.
1. Initially queue is empty : front =0 and Rear=0.
2. Add A in the queue. after adding A in queue front will be increased by 1 and rear will be increased by 1.
front=1 Rear=1
3. Add B and C in the queue . As 2 elements have been added rear will be increased by 2 and front will remain the same.
front =1 Rear=3
4 Delete B from the queue .As element has been deleted hence front will be increased by 1 and rear will remain the same.
Please comment if you find any mistake in post.
No comments:
Post a Comment