How to implement a priority singly linked queue

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

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();
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);         }      }

Share the Post:
Share on facebook
Share on twitter
Share on linkedin


The Latest

technology leadership

Why the World Needs More Technology Leadership

As a fact, technology has touched every single aspect of our lives. And there are some technology giants in today’s world which have been frequently opined to have a strong influence on recent overall technological influence. Moreover, those tech giants have popular technology leaders leading the companies toward achieving greatness.

iOS app development

The Future of iOS App Development: Trends to Watch

When it launched in 2008, the Apple App Store only had 500 apps available. By the first quarter of 2022, the store had about 2.18 million iOS-exclusive apps. Average monthly app releases for the platform reached 34,000 in the first half of 2022, indicating rapid growth in iOS app development.

microsoft careers

Top Careers at Microsoft

Microsoft has gained its position as one of the top companies in the world, and Microsoft careers are flourishing. This multinational company is efficiently developing popular software and computers with other consumer electronics. It is a dream come true for so many people to acquire a high paid, high-prestige job