An Array Implementation of a Priority Queue
The following implementation uses a sorted array based on the priority value. The sort order will be from smallest to largest (i.e. the item with the highest priority is always the last item in the array).
class PriorityQueue { Object data[]; int maxItems, numberOfItems; public PriorityQueue(int size) { maxItems = size; data = new Object[maxItems]; numberOfItems = 0; } public boolean isEmpty() { return numberOfItems == 0; } public void insert(Object item) { int position = numberOfItems-1; while (position >= 0 && data[position].pValue >= item.pValue) { data[position+1] = data[position]; --position; } data[position+1] = item; ++numberOfItems; } public Object delete() { --numberOfItems; return data[numberOfItems]; } }
Although this implementation is simple, it posseses two limitations:
A Linked List Implementation of a Priority Queue
The following implementation uses a sorted linked list based on the priority value. The sort order will be from largest to smallest (i.e. the item with the highest priority is always the first item in the list).
This implementation will use a node with the following structure:
class PQNode { Object data; PQNode next; public PQNode(Object value) { this.data = value; this.next = null; } }
The priority queue can then be implemented as follows:
class PriorityQueue { PQNode head; public PriorityQueue() { this.head = null; } public boolean isEmpty() { return this.head == null; } public void insert(Object item) { PQNode prev = null; PQNode current = this.head; while (current != null && current.data.pValue >= item.pValue) { prev = current; current = current.next; } PQNode temp = new PQNode(item); if (prev == null) { temp.next = this.head; this.head = temp; } else { temp.next = current; prev.next = temp; } } public Object delete() { Object temp = this.head.data; this.head = this.head.next; return temp; } }
Although this implementation eliminates the first limitation of the array implementation, it still posseses the same efficiency problem: