QUEUE ADT
“A queue is an ordered list in which all inse at another end called FRONT”. squeue are some times referred to as First In First Out (FIFO) lists.
Example
1. The people waiting in line at a bank cash counter form a queue.
2. In computer, the jobs waiting in line to use the processor for execution. This queue is
called Job Queue.
Operations Of Queue
There are two basic queue operations. They are,
Enqueue –Inserts an item / element at the rear end of the queue. An error occurs if the queue is full.
Dequeue –Removes an item / element from the front end of the queue, and returns it to the user. An error occurs if the queue is empty.
1. Addition into a queue
procedure addq (item : items);
{add item to the queue q}
begin
if rear=n then queuefull
else begin
rear :=rear+1; q[rear]:=item;
end;
end;
{of addq}
2. Deletion in a queue
procedure deleteq (var item : items);
{delete from the front of q and put into item}
begin
if front = rear then queueempty
else begin
front := front+1
item := q[front];
end;
end
Uses of Queues ( Application of queue )
Queues remember things in first-in-first-out (FIFO) order. Good for fair (first come first served) ordering of actions.
Examples of use: (Application of stack )
1• scheduling
processing of GUI events printing request
2• simulation orders the events
models real life queues (e.g. supermarkets checkout, phone calls on hold)
CIRCULAR QUEUE IMPLEMENTATION:
Location of queue are viewed in a circular form. The first location is viewed after the last one. Overflow occurs when all the locations are filled.
Algorithm Circular Queue Insert
Void CQInsert ( int queue[ ], front, rear, item)
{
if ( front = = 0 )
front = front +1;
if ( ( ( rear = maxsize ) && ( front = = 1 ) ) || ( ( rear ! = 0 ) && ( front = rear +1)))
{
printf( “ queue overflow “);
if( rear = = maxsize ) rear = 1;
else
rear = rear + 1; q [ rear ] = item;
}
}
Algorithm Circular Queue Delete int CQDelete ( queue [ ], front, rear )
{
if ( front = = 0 )
printf ( “ queue underflow “);
else
{
item = queue [ front ]; if(front = = rear )
{
front = 0; rear = 0;
}
else if ( front = = maxsize )
{
front = 1;
}
else
front = front + 1;
}
return item;
}
DOUBLE ENDED QUEUE IMPLEMENTATION
A deque (short for double-ended queue) is an abstract data structure for which elements can be added to or removed from the front or back(both end). This differs from a normal queue, where elements can only be added to one end and removed from the other. Both queues and stacks can be considered specializations of deques, and can be implemented using dequeue.
Two types of Dqueue are
1. Input Restricted Dqueue
2. Ouput Restricted Dqueue.
1. Input Restricted Dqueue
Where the input (insertion) is restricted to the rear end and the deletions has the options either end
2. Ouput Restricted Dqueue.
Where the output (deletion) is restricted to the front end and the insertions has the option either end.
Example: Timesharing system using the prototype of priority queue –programs of high priority are processed first and programs with the same priority form a standard queue.
Priority Queue
A priority queue is a collection of elements such that each element has been assigned a priority and such that the order in which elements are deleted and processed comes from the following rules:
1. An element of higher priority is processed before any element of lower priority.
2. Two elements with the same priority are processed according to the order in which they were added to the queue.
Two types of queue are
1. Ascending Priority Queue
2. Descending Priority Queue
1. Ascending Priority Queue
Collection of items into which item can be inserted arbitrarily & from which only the Smallest item can be removed.
2. Descending Priority Queue
Collection of items into which item can be inserted arbitrarily & from which only the Largest item can be removed.
APPLICATIONS OF QUEUE
Batch processing in an operating system To implement Priority Queues.
Priority Queues can be used to sort the elements using Heap Sort. Simulation and Mathematics user Queueing theory.
Computer networks where the server takes the jobs of the client as per thequeue strategy.
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.