How to implement a priority singly linked queue

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:
XDR solutions

The Benefits of Using XDR Solutions

Cybercriminals constantly adapt their strategies, developing newer, more powerful, and intelligent ways to attack your network. Since security professionals must innovate as well, more conventional endpoint detection solutions have evolved

AI is revolutionizing fraud detection

How AI is Revolutionizing Fraud Detection

Artificial intelligence – commonly known as AI – means a form of technology with multiple uses. As a result, it has become extremely valuable to a number of businesses across

AI innovation

Companies Leading AI Innovation in 2023

Artificial intelligence (AI) has been transforming industries and revolutionizing business operations. AI’s potential to enhance efficiency and productivity has become crucial to many businesses. As we move into 2023, several

data fivetran pricing

Fivetran Pricing Explained

One of the biggest trends of the 21st century is the massive surge in analytics. Analytics is the process of utilizing data to drive future decision-making. With so much of

kubernetes logging

Kubernetes Logging: What You Need to Know

Kubernetes from Google is one of the most popular open-source and free container management solutions made to make managing and deploying applications easier. It has a solid architecture that makes

ransomware cyber attack

Why Is Ransomware Such a Major Threat?

One of the most significant cyber threats faced by modern organizations is a ransomware attack. Ransomware attacks have grown in both sophistication and frequency over the past few years, forcing

data dictionary

Tools You Need to Make a Data Dictionary

Data dictionaries are crucial for organizations of all sizes that deal with large amounts of data. they are centralized repositories of all the data in organizations, including metadata such as