A Textbook of Data Structures and Algorithms, Volume 1

5Queues

In this chapter, we discuss the queue data structure, its operations and its variants, namely, circular queues, priority queues and deques. The application of the data structure is demonstrated on the problem of job scheduling in a time-sharing system environment.

5.1. Introduction

A queue is a linear list in which all insertions are made at one end of the list known as the rear or tail of the queue, and all deletions are made at the other end known as the front or head of the queue. An insertion operation is also referred to as enqueuing a queue, and a deletion operation is referred to as dequeuing a queue.

Figure 5.1 illustrates a queue and its functionality. Here, Q is a queue of three elements a, b, and c (Figure 5.1(a)). When an element d is to join the queue, it is inserted at the rear end of the queue (Figure 5.1(b)), and when an element is to be deleted, the element at the front end of the queue, namely, a, is deleted automatically (Figure 5.1(c)). Thus, a queue data structure obeys the principle of First In First Out (FIFO) or First Come First Served (FCFS).

Many examples of queues occur in everyday life. Figure 5.2(a) illustrates a queue of customers waiting to be served by a clerk at the booking counter, and Figure 5.2(b) illustrates a trail of components moving down an assembly line to be processed by a robot at the end of the line. The FIFO principle of insertion at the rear end of the queue when a new client arrives or when a new component is added, and ...