Page 168 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 10: Queues

in which they arrive i.e. first in first out (FIFO) order. In most cases, the first customer in the Notes
queue is the first to be served.

10.1 Representation of Linear Queue

A physical analogy for a queue is a line at a booking counter. At a booking counter, customers
go to the rear (end) of the line and customers are attended to various services from the front of
the line. Unlike stack, customers are added at the rear end and deleted from the front end in a
queue (FIFO).

Example: An example of the queue in computer science is print jobs scheduled for
printers. These jobs are maintained in a queue. The job fired for the printer first gets printed first.
Same is the scenario for job scheduling in the CPU of computer.

Did u know? Like a stack, a queue also (usually) holds data elements of the same type.
We usually graphically display a queue horizontally. Figure 10.1 depicts a queue of 5 characters.

Figure 10.1: A Queue of Characters

The rule followed in a queue is that elements are added at the rear and come off of the front of
the queue. After the addition of an element to the above queue, the position of rear pointer
changes as shown below. Now the rear is pointing to the new element ‘g’ added at the rear of the
queue.

Figure 10.2: Queue of Figure 10.1 after Addition of New Element

After the removal of element ‘a’ from the front, the queue changes to the following with the
front pointer pointing to ‘b’
Figure 10.3: Queue of Figure 10.2 after Deletion of an Element

LOVELY PROFESSIONAL UNIVERSITY 161