Question

// priorityList.java
// a priority queue based on a sorted list
// to run this program: C>java PiorityQApp
////////////////////////////////////////////////////////////////
class Link
   {
   public long dData;                  // data item
   public Link next;                   // next link in list
// -------------------------------------------------------------
   public Link(long dd)                // constructor
      { dData = dd; }
// -------------------------------------------------------------
   public void displayLink()           // display this link
      { System.out.print(dData + " "); }
   }  // end class Link
////////////////////////////////////////////////////////////////
class SortedList
   {
   private Link first;                 // ref to first item
// -------------------------------------------------------------
   public SortedList()                 // constructor
      { first = null; }
// -------------------------------------------------------------
   public boolean isEmpty()            // true if no links
      { return (first==null); }
// -------------------------------------------------------------
   public void insert(long key)        // insert, in order
      {
      Link newLink = new Link(key);    // make new link
      Link previous = null;            // start at first
      Link current = first;
                                       // until end of list,
      while(current != null && key > current.dData)
         {                             // or key > current,
         previous = current;
         current = current.next;       // go to next item
         }
      if(previous==null)               // at beginning of list
         first = newLink;              // first --> newLink
      else                             // not at beginning
         previous.next = newLink;      // old prev --> newLink
      newLink.next = current;          // newLink --> old currnt
      }  // end insert()
// -------------------------------------------------------------
   public Link remove()           // return & delete first link
      {                           // (assumes non-empty list)
      Link temp = first;               // save first
      first = first.next;              // delete first
      return temp;                     // return value
      }
// -------------------------------------------------------------
   public void displayList()
      {
      Link current = first;       // start at beginning of list
      while(current != null)      // until end of list,
         {
         current.displayLink();   // print data
         current = current.next;  // move to next link
         }
      }
   }  // end class SortedList
////////////////////////////////////////////////////////////////
class PriorityQ
   {
   private SortedList theList;
//-------------------------------------------------------------
   public PriorityQ()               // constructor
      {
      theList = new SortedList();
      }
//-------------------------------------------------------------
   public void insert(long item)    // insert item
      {
           // TBD - NEED TO DO INSERT HERE
      }
//-------------------------------------------------------------
   public long remove()             // remove minimum item
      {
          // TBD - THIS SHOULD REMOVE THE FIRST ITEM FROM AND LIST AND RETURN THE DATA VALUE OF THE LINK REMOVED
      }
//-------------------------------------------------------------
   public boolean isEmpty()         // true if queue is empty
      {
         // TBD - THIS SHOULD RETURN WHETHER THE QUEUE IS EMPTY OR NOT
      }
//-------------------------------------------------------------
   }  // end class PriorityQ
////////////////////////////////////////////////////////////////
class PriorityQApp
   {
   public static void main(String[] args)
      {
      PriorityQ thePQ = new PriorityQ();

      thePQ.insert(30);
      thePQ.insert(50);
      thePQ.insert(10);
      thePQ.insert(40);
      thePQ.insert(20);

      while( !thePQ.isEmpty() )
         {
         long item = thePQ.remove();
         System.out.print(item + " ");  // 10, 20, 30, 40, 50
         }  // end while
      System.out.println("");
      }  // end main()
//-------------------------------------------------------------
   }  // end class PriorityQApp

Implement a priority queue based on a sorted linked list.

I have provided the code to get started in file priorityList.java.  This code consists of the sorttedlist.java program from listing 5.6, along with the main app class (class PriorityQApp) from the PriorityQ.java from Listing 4.6.  I have added a shell class PriorityQ, which will be the ADT, as this will implement a Priority Queue based on the underlying sorted linked list.You assignment will be to then add code to the 3 methods from within the class PriorityQ (the methods have a comment "// TBD") - to make it all work.  Once you add the methods, you should test it to verify it works.Note, that the remove operation on the priority queue should remove the item with the smallest key.

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

class Link {
        public long dData; // data item
        public Link next; // next link in list

        // -------------------------------------------------------------

        public Link(long dd) // constructor
        {
                dData = dd;
        }

        // -------------------------------------------------------------
        public void displayLink() // display this link
        {
                System.out.print(dData + " ");
        }
} // end class Link
// //////////////////////////////////////////////////////////////

class SortedList {
        private Link first; // ref to first item

        // -------------------------------------------------------------

        public SortedList() // constructor
        {
                first = null;
        }

        // -------------------------------------------------------------
        public boolean isEmpty() // true if no links
        {
                return (first == null);
        }

        // -------------------------------------------------------------
        public void insert(long key) // insert, in order
        {
                Link newLink = new Link(key); // make new link
                Link previous = null; // start at first
                Link current = first;
                // until end of list,
                while (current != null && key > current.dData) { // or key > current,
                        previous = current;
                        current = current.next; // go to next item
                }
                if (previous == null) // at beginning of list
                        first = newLink; // first --> newLink
                else
                        // not at beginning
                        previous.next = newLink; // old prev --> newLink
                newLink.next = current; // newLink --> old currnt
        } // end insert()
                // -------------------------------------------------------------

        public Link remove() // return & delete first link
        { // (assumes non-empty list)
                Link temp = first; // save first
                first = first.next; // delete first
                return temp; // return value
        }

        // -------------------------------------------------------------
        public void displayList() {
                Link current = first; // start at beginning of list
                while (current != null) // until end of list,
                {
                        current.displayLink(); // print data
                        current = current.next; // move to next link
                }
        }
} // end class SortedList
// //////////////////////////////////////////////////////////////

class PriorityQ {
        private SortedList theList;

        // -------------------------------------------------------------
        public PriorityQ() // constructor
        {
                theList = new SortedList();
        }

        // -------------------------------------------------------------
        public void insert(long item) // insert item
        {
                // simply inserting item to sorted list
                theList.insert(item);
        }

        // -------------------------------------------------------------
        public long remove() // remove minimum item
        {
                // removing first link from sorted list (link with smallest value), and
                // returning data of removed link. assuming queue is not empty.
                return theList.remove().dData;
        }

        // -------------------------------------------------------------
        public boolean isEmpty() // true if queue is empty
        {
                // returns true if underlying sortedlist is empty
                return theList.isEmpty();
        }
        // -------------------------------------------------------------
} // end class PriorityQ
// //////////////////////////////////////////////////////////////

class PriorityQApp {
        public static void main(String[] args) {
                PriorityQ thePQ = new PriorityQ();

                thePQ.insert(30);
                thePQ.insert(50);
                thePQ.insert(10);
                thePQ.insert(40);
                thePQ.insert(20);

                while (!thePQ.isEmpty()) {
                        long item = thePQ.remove();
                        System.out.print(item + " "); // 10, 20, 30, 40, 50
                } // end while
                System.out.println("");
        } // end main()
                // -------------------------------------------------------------
} // end class PriorityQApp

/*OUTPUT*/

10 20 30 40 50