Page 171 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes Figure 10.5 depicts the linked list representation of a queue.
Figure 10.5: A Linked List representation of a Queue

Self Assessment

Fill in the blanks:
1. The rule followed in a queue is that elements are added at the ....................... and come off
of the front of the queue.

2. The stack and the queue differ only in the position where the ....................... can be added or
deleted.
3. The object that holds the data and refers to the next element in the list is called a .......................

10.2 Representation of Multiple Queues

So far, we have seen the representation of a single queue, but many practical applications in
computer science require several queues. Multiqueue is a data structure where multiple queues
are maintained. This type of data structures are used for process scheduling. We may use one
dimensional array or multidimensional array to represent a multiple queue.

Figure 10.6: Multiple Queues in an Array

A multiqueue implementation using a single dimensional array with m elements is depicted in
Figure 10.6. Each queue has n elements which are mapped to a liner array of m elements.

Self Assessment

State whether the following statements are true or false:
4. Linear queue is a data structure where multiple queues are maintained.
5. Multiqueues are used for process scheduling.

10.3 Representation of a Circular Queue

One of the major problems with the linear queue is the lack of proper utilization of space.
Suppose that the queue can store 100 elements and the entire queue is full. So, it means that the

164 LOVELY PROFESSIONAL UNIVERSITY