Page 137 - DCAP407_DATA_STRUCTURE

Data Structure

queue, for access to disk storage or for using the CPU. The queues in a bank, or railway station counter
are examples of queue. The first person in the queue is the first to be attended.
The two main operations in the queue are insertion and deletion of items. The queue has two pointers,
the front pointer points to the first element of the queue and the rear pointer points to the last element
of the queue. Figure 8.1 shows the structure of a queue. A new item is inserted at the rear end and
elements are removed from the queue from the front end.

Figure 8.1: Queue Structure

8.2 Basic Operations of Queue
The basic operations of queue are insertion and deletion of items which are referred as enqueue and
dequeue respectively. In enqueue operation, an item is added to the rear end of the queue. In dequeue
operation, the item is deleted from the front end of the queue.
8.2.1 Insert at Rear End
To insert an item into the queue, first it should be verified whether the queue is full or not. If the queue
is full, a new item cannot be inserted into the queue. The condition FRONT=NULL indicates that the
queue is empty. If the queue is not full, items are inserted at the rear end. When an item is added to the
queue, the value of rear is incremented by 1.
8.2.2 Delete from the Front End
To delete an item from the stack, first it should be verified that the queue is not empty. If the queue is
not empty, the items are deleted at the front end of the queue. When an item is deleted from the queue,
the value of the front is incremented by 1.
Figure 8.2 is a representation of the basic operations of a queue. The first element inserted into the
queue is 10, the second element inserted is 15 and so on. 30 is the last inserted element. The first element
to be deleted from the queue is 10. If a new element is added, it is inserted after 30 and it will be the last
element in the queue. A new element cannot be inserted in the queue when the queue is full.

Figure 8.2: Operations in Queue

130 LOVELY PROFESSIONAL UNIVERSITY