COMP 210: Data Structures

Priority Queues

Introduction and Definition

A Priority Queue is a variation of the Queue ADT. The basic idea of this structure is similar to that of a queue, in that we have elements waiting in line for a service. It differs from a queue in that selection is not on a strictly first-come, first-serve basis; it also takes into account some type of priority. For example, patients in an emergency waiting room are treated based on the severity of their injuries, not on when they arrived. In air traffic control, there is a queue of planes waiting to land, but the controller can move a plane to the front of the line if the plane is low on fuel, or there is a sick passenger on board.

Stop and Think:

Consider implementing a PriorityQueue with the following data structures. Consider the pros and cons of each structure, including the time to add and remove elements from the PriorityQueue.

• Store the elements in a Queue object.
• Store the elements in an array of queues, with one array entry for each priority.
• Store the elements in an ArrayList, ordered by highest priority.
• Store the elements in a LinkedList, ordered by highest priority.
• Are there other data structures you might consider?