Question

Discuss the queue data structure.

What are its unique structural and behavioral concepts?

What are its most frequently used methods?

What implementations are provided?

What practical applications does it support?

Discuss the priority queue variant.

Answer 1

A queue is an ordered collection of elements into which insertion is done at one end called rear, and deletion is done at the other end called front. It follows a First-in First-out structure. The most frequently used methods include: insert() which will insert the key into the rear end of the queue. deletion() which will delete the key into the front end of the queue. The queue data structure can be implemented using either an array, or a linked list. The limitation of an array implementation is that, the size of the queue is limited, and it cannot be either expanded or shrinked. Inserting elements beyond the pre-defined array size leads to queue full case, and deleting elements beyond the zero size leads to queue empty case. Whereas, in linkedlist implementation, the queue full case will not arise, whereas, the queue empty case could arise always. The practical applications that will be implemented by queue include, the CPU which processes the programs/processes in the first-in first-out fashion. The other applications includes handling the interrupts in the real-time system. The interrupts will be served in the first-come first-server order. The priority queue variant is an advanced concept of a queue. Each element in the queue is assigned a priority, and the high priority elements are served(removed from the queue) first, when compared to low priority elements. If multiple elements of same priority exist in the queue, then again they will be searched in the first-in first-out fashion.