Question:
I would like to know how I can implement a priority singly linked queue.

Answer:
I like to think of priority queue as a possible implementation of the standard queue ADT:

interface Queue {   public void enqueue(Object item);   public void dequeue();   public Object getFront() throws EmptyQueueException;   public boolean isEmpty();   public boolean isFull();}

where the empty queue exception is:

class EmptyQueueException extends RuntimeException {   public EmptyQueueException() {      super(“Empty Queue: Queue is empty!”);   }   public EmptyQueueException(String gripe) {      super(“Empty Queue: ” + gripe);   }}

Notice that generic objects are queued.

The preferred priority queue implementation would be a balancedtree or a 2-3 tree, since this gives a O(lg(n)) complexity for enqueue and dequeue, where n = queue length:

class BTree implements Queue { … }

A linked list implementation gives a O(n) complexity for eitherenqueue or dequeue, depending on the details.

One advantage of the linked list implementation is that it canbe defined as a simple extension of the linked list implementation for FIFO queues.

A linked list implementation stores data items in (what else?) a linked list, which is made of cells. The “item”field of a cell actually stores the data, while the “next” fieldrecursively points to the next cell in the list. To maintainreusability, we will assume the data stored in a cell is of typeObject:

class Cell {   private Object item; // car   private Cell next;   // cdr   public Cell() {      item = null;      next = null;   }     public Cell(Object thing) {       item = thing;      next = null;   }   public Cell(Object thing, Cell cell) {      item = thing;      next = cell;   }   public Object getItem() { return item; }   public Cell getNext() { return next; }   public void setItem(Object thing) { item = thing; }   public void setNext(Cell cell) { next = cell; }}

The standard FIFO queue maintains references to thefront and rear cells of the linked list holding itsdata items. Enqueueing and dequeueing cells is simplya matter of changing front and rear:

class FIFOQueue implements Queue {   // leave these protected so they can be   // manipulated in extensions   protected Cell front, rear;      public FIFOQueue() {      front = null;      rear = null;   }   public boolean isEmpty() {      return front == null;   }   public boolean isFull() {      return false; // never happens!   }   public void enqueue (Object item) {      Cell cell = new Cell(item);      if (rear == null) { // hence front == null         rear = cell;         front = cell;      }      else {         rear.setNext(cell);         rear = cell;      }   }   // we can compare cells with == because Java’s = uses pointer semantics   public void dequeue() {      if (front != null)  // no effect o.w.         if (front == rear) { // one item in queue            front = null;            rear = null;         }         else            front = front.getNext(); // old front becomes garbage   }   public Object getFront() throws EmptyQueueException {      if (front != null)         return front.getItem();      else          throw(new EmptyQueueException());   }}

A linked list implementation of a priority queue will extend thedefinition of FIFO queue just given. We will assume data stored in the linked list is sorted according to priority, so the first item(i.e. front.item()) has the highest priority. This means we just need to overwrite enqueue so that it inserts new items accordingto their priorities.

One problem is that not all objects have a natural priority. How dowe define a generic priority queue? Priority queue storables mustbe ordinals, where an ordinal is any class that supports an integer valued priority function:

interface Ordinal {   abstract int priority();}

In other words, any class of objects we wish to store in a priorityqueue must implement the ordinal interface. For example:

class Widget implements Ordinal { // extends ???   private int value;   public Widget() { value = 0; }   public Widget(int i) { value = i; }   public int getVal() { return value; }   // etc.   public int priority() {      return value * value + 1;   }}

A priority queue needs only to overwrite the enqueuemethod inherited from FIFOQueue.

class PriorityQueue extends FIFOQueue {   // probably don’t need this:   public PriorityQueue() { super(); }   // a little utility   // = cell.getItem().priority()   private int pri(Cell cell) {      Ordinal item = (Ordinal)(cell.getItem());      if (item == null)        return -1;      else        return item.priority();   }   // overwrites LinkedQueue.enqueue()   public void enqueue(Object obj) { … }}

The standard trick for inserting an ordinal, ord, intoa linked list is to maintain two cell references: next and afterNext, where afterNext is next.getNext(). As we traverse the cells in the linked list, we update these two references:

next = afterNext;   afterNext = next.getNext();

until

afterNext.getItem().priority() < ord.priority()

at which point we insert ord into the list:

Cell cell = new Cell(ord, afterNext);   next.setNext(cell);

Here’s the code. Note that special care must be takenwhen ord is inserted at the front or rear of the queue:

public void enqueue(Object obj) {      if (isEmpty())         super.enqueue(obj);       else {         if (!(obj instanceof Ordinal)) {            System.err.println(obj.toString() + ” must be an ordinal”);            System.exit(1);         }         Ordinal ord = (Ordinal)obj;         int rank = ord.priority();         if (pri(front) < rank) {            Cell cell = new Cell(ord, front);            front = cell;         }         Cell next = front;          Cell afterNext = next.getNext();         while (afterNext != null && pri(afterNext) > rank) {            next = afterNext;            afterNext = next.getNext();         } // while         if (afterNext == null)            super.enqueue(ord); // just put it at the end         else {            Cell cell = new Cell(ord, afterNext);            next.setNext(cell);         } // else      } // else   }  // enqueue

Here’s a piece of code that prints and empties a priority queue, q, filled with widgets:

while(!q.isEmpty()) {         try {            Widget u = (Widget)(q.getFront());            q.dequeue();            System.out.println(“next item = ” + u.getVal());         }         catch(EmptyQueueException eqe) {            System.err.println(eqe.toString());            System.exit(1);         }      }