Page 178 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 10: Queues

Return Item Notes
Step 6 Exit

10.4.2 Linked List Implementation of Priority Queue

Another way to represent a priority queue in memory is by means of one-way list:

Each node in the list contains three items of information – an information field INFO, a
priority number PRNO and the link NEXT.

Node A will precede Node B in the list when A has higher priority than B or when both the
nodes have same priority but A was added to the list before B.

!

Caution The order in one-way list corresponds to the order of priority queue.
Figure 10.8 shows priority queue with 4 elements where B and C have same priority numbers.

Figure 10.8: Priority Queue with 4 Elements

Source: http://www.eshikshak.co.in/index.php/data-structure/queue/priority-queue

Self Assessment

Fill in the blanks:
8. A ......................... is a collection of elements where each element is assigned a priority.

9. An element of higher priority is processed before any element of ......................... priority.
10. Two elements with the same priority are processed according to the ......................... in
which they are added to the queue.

11. Deleting an element with the ......................... priority would require examining the entire
array to search for such an element.
12. The ......................... of priority queue holds the type of data item, priority of the element
and the order in which the element has been added.

10.5 Representation of Dequeue

Dequeue (a double ended queue) is an abstract data type similar to queue, where addition and
deletion of elements are allowed at both the ends. Like a linear queue and a circular queue, a
dequeue can also be implemented using arrays or linked lists.

10.5.1 Array Implementation of a Dequeue

If a Dequeue is implemented using arrays, then it will suffer with the same problems that a
linear queue had suffered. Program given below gives the array implementation of a Dequeue.
#include “stdio.h”
#define QUEUE_LENGTH 10;

LOVELY PROFESSIONAL UNIVERSITY 171