Login | Register   
LinkedIn
Google+
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


Tip of the Day
Language: Java Language
Expertise: Beginner
May 27, 1997

How to implement a priority singly linked queue

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 balanced tree 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 either enqueue or dequeue, depending on the details.

One advantage of the linked list implementation is that it can be 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" field recursively points to the next cell in the list. To maintain reusability, we will assume the data stored in a cell is of type Object:

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 the front and rear cells of the linked list holding its data items. Enqueueing and dequeueing cells is simply a 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 the definition 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 according to their priorities.

One problem is that not all objects have a natural priority. How do we define a generic priority queue? Priority queue storables must be 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 priority queue 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 enqueue method 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, into a 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 taken when 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);
         }
      }
DevX Pro
 
Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap
Thanks for your registration, follow us on our social networks to keep up-to-date