Priority Queues

Introduction

A queue is one of the many data structures that are found in the field of computer science. As the name itself explains, this data structure is one that symbolizes or shows a list of items positioned one after another in a list that can be processed by the system.

This report emphasizes more on Priority Queues. Priority Queues are a form of data structure that extends another data structure, the Queues. This implies that Priority Queues have the same field sets that the Queues have but differ in certain behaviours.

The report then will focus more on firstly the description of the Priority Queue class, the applications of the class and finally a discussion of the benefits and limitations of using the Priority Queues

DESCRIPTION OF PRIORITY QUEUES

A priority queue is a data structure for maintaining a collection of items that are in order of priority or importance (Bailey, 2003), unlike the original Queue data structure where items were ordered in the first-in-first-out basis. The defined priority in the queue sets the order in which the objects in the queue exit – where the item with the highest priority exits the queue first (Oracle 1993).

The priority Queue class supports insertion of items with their priority known (Oracle, 1993). Keeping in memory the item of maximum or minimum priority as well as procedure to extract that maximum or minimum object.

APPLICATION OF PRIORITY QUEUES

The simplest application of a priority queue would be to use it in arithmetic. For example, when designing a method to find the maximum in a list of numbers. This application is fairly simple and easy to understand. Chazelle (2000) elaborates that there are more Computer Science based applications of priority queues, Event Driven Simulations, Numerical Computation, Data Compression, Graph Searching and Spam Filtering to name a few.

One noted use of priority queue in event driven simulations is in molecular dynamics, as Gerald (2006) shows in his journal. Gerald...