Question

3. Some circular queue implementations use the mod operator % in enqueue and dequeue operations. Explain why this is inefficient. 4. If a queue is implemented using a singly linked list with a head and tail pointer, you should always insert at the tail and remove from the head. Explain why this is so. 5. What is a Priority Queue, and how does it differ from a standard queue? 6. Priority Queues are almost always implemented with an ordered data structure. Why?

Answer 1

Answer 3:

A circluar queue is like a circle which do not have isolated front and rear ends or we can say front and rear ends are merged together in order to form a circle. Suppose we have normal linear empty queue of length 5, so intially both front and rear end will be on index 0, now as soon as we start inserting elements in queue rear end starts moving by step 1. If rear end reaches at the max length of queue i.e; at index 4, then queue is full. If we pop element from full queue then index 0 will get empty and now again we can insert a element at index 0 because we have made over queue circular that's why we can jump on index 0 from index 4 but to achieve this we need to take mod (%) of (rear+1) with size of queue, in order to get next empty index i.e rear = (rear+1)%size

---------------------------------------------------------------------------------

Answer 4:

Because queue is FIFO data structure that means first in first out. To achieve this property while implementing queue as singly linked list we insert element from tail and remove element from head.

----------------------------------------------------------------------------------

Answer 5:

A priority queue is like a normal queue but there is one extra property in it which is "priority" i.e; each elements in priority queue has it's own priority value and element with highest priority is served first before low priority element. Priority queue data structure is used in mostly process scheduling algorithm.

-----------------------------------------------------------------------------

Answer 6:

Because to choose elements based on their priorities they must arranged in some order. For example, Binary search tree where left node is smaller than root and right node is greater than root. So if elements are set in any order then we can decide priority of any elements i.e; we will get know what we should pick next.