Page 93 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 4.3 Applications of Queues

One major application of the queue data structure is in the computer simulation of a real-world
situation. Queues are also used in many ways by the operating system, the program that schedules
and allocates the resources of a computer system. One of these resources is the CPU (Central
Processing Unit) itself. If you are working on a multi-user system and you tell the computer
to run a particular program, the operating system adds your request to its “job queue”. When
your request gets to the front of the queue, the program you requested is executed. Similarly, the
various users for the system must share the I/O devices (printers, disks etc.). Each device has its
own queue of requests to print, read or write to these devices. The following subsection discusses
one application of the queues – the priority queue. It is used in time-sharing multi-user systems
where programs of high priority are processed fi rst arid programs with the same priority form
a standard queue.

Priority Queues

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 is defined by the following

rules:
An element of higher priority is processed before any element of lower priority. Two elements
with the same priority are processed according to the order in which they were inserted into the
queue.
We would use a singly linked list to implement the priority queue. Each node of the linked list

would have a type definition as follows:
struct qElement
{
T item;
int priority;
qElement *next;
} *Pqueue, *front, *rear;
The algorithm for the insertion would change now. Insertion would insert the new element at
the correct position according to the priority of the element. The elements of the priority queue
would be sorted in a non-descending order of the priority with the front of the queue having the
element with the highest priority. The deletion procedure need not change since the element at
the front is the one with the highest priority and that is the one that should be deleted.
void insert(Pqueue *front, Pqueue *rear, T e, int p)
/* this inserts an element having data e and priority p into the priority queue
*/
/*the insertion maintains the sorted order of the priority queue */
{
Pqueue *f, *r;
Pqueue *x;
int pr;
{
x = new(Pqueue);
x->item = e; x->priority = p;

88 LOVELY PROFESSIONAL UNIVERSITY