Page 99 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 4.4 Summary

A queue is a list of elements in which insertions are made at one end – called the rear and
deletions are made from the other end - called the front.
A queue exhibits the FIFO (First In First Out) property. To represent a queue we require a
one-dimensional array of some maximum size say n to hold the data items and two other
variables front and rear to point to the beginning and the end of the queue.
As in stacks, a queue could be implemented using a linked list. 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. Each device has its own queue of requests
to print, read or write to these devices.
A priority queue is a collection of elements such that each element has been assigned a
priority. 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.

4.5 Keywords

FIFO: (First In First Out) The property of a linear data structure which ensures that the element
retrieved from it is the first element that went into it.

Front: The end of a queue from where elements are retrieved.
Queue: A linear data structure in which the element is inserted at one end while retrieved from
another end.
Rear: The end of a queue where new elements are inserted.

4.6 Self Assessment

Choose the appropriate answer:

1. Priority queue is a
(a) Collection of elements such that each element has been assigned a priority.
(b) Collection of I/O devices
(c) Collection of FIFO
(d) None of the above

2. Every insertion implies that the rear of the queue increases by 1 except when rear =.
(a) n-2
(b) n-1
(c) n-0

(d) n-3
Fill in the blanks:
3. During the initialization of a queue q, its front and rear are made to .................................

94 LOVELY PROFESSIONAL UNIVERSITY