Page 142 - DCAP407_DATA_STRUCTURE

Unit 8: Queues

Use the diagram depicted below to implement queue using linked list:

8.4 Types of Queue

The different types of queue are:
1. Double ended queue
2. Circular queue
3. Priority queue

8.4.1 Double Ended Queue
Double ended queue is also known as deque. It is a type of queue where the insertions and deletions
happen at the front or the rear end of the queue. The various operations that can be performed on the
double ended queue are:
1. Insert an element at the front end
2. Insert an element at the rear end
3. Delete an element at the front end
4. Delete an element at the rear end

Let us now discuss how an element can be inserted at the front end and deleted at the rear end of a
deque. Figure 8.4 depicts inserting and deleting an element from deque. The front end of the queue is
identified by F and the rear end is identified by R. If we want to insert an element 20 at the front end,
we can do this by checking if F is equal to zero and then increment F and insert the element. We cannot
insert an element at the front if an element is already present at the first position, as queue follows ‘First
In First Out’ method. In the figure 8.4, the element 30 is already present in the first position of the
queue. Hence, we cannot insert an element at the front end. If we want to delete element 60 at the rear
end, access the element at the rear end and then decrement the pointer R. When the elements are
deleted and queue becomes empty, reset the pointer F to 0 and rear end pointer R to -1. An element can
be deleted only if the queue is not empty.

LOVELY PROFESSIONAL UNIVERSITY 135