7 Replies Latest reply: Nov 29, 2006 1:12 AM by EJP RSS

    Priority Queue as a LinkedList

    807599
      Hello everyone. I'm having problems trying to figure out exactly how to implement this code. Please, I just want a bump in the right direction, I'm not asking for people to complete the code, just a bit of help. Therre are three classes the first two shown are complete but the last one I am having problems with.
      import java.io.*;
      public class Date implements InOutputable
      {
           private String month, day, year;
           
           public Date()
           {
                this.month = " ";
                this.day = " ";
                this.year = " ";
           }
           public void input (BufferedReader reader) throws IOException
           {
                String date = reader.readLine();
                int slash = date.indexOf('/');
                month = date.substring(0, slash);
                day = date.substring(slash + 1);
                year = date.substring(slash + 2);
           }
           public void output(Printstream writer)
           {
                writer.println(toString());
           }
           public String toString()
           {
                return month.substring(0, 2);
           }
           public int compareTo(Object other)
           {
                Date otherDate = (Date)other;
                if (year.equals(otherDate.year) && (month.equalsIgnoreCase
                     (otherDate.month))
                          return day.compareTo(otherDay.day);
                if (year.equals(otherDate.year) && !month.equalsIgnoreCase
                     (otherDate.month))
                          return month.toLowerCase().compareTo
                               (otherDate.month.toLowerCase());
                return year.compareTo(otherDate.year);
           }
           public boolean equals (InOutputable other)
           {
                Date otherDate = (Date) other;
                return month.equalsIgnoreCase (otherDate.month) &&
                     day.equals (otherDate.day) && year.equals(otherDate.year);
           }
           public boolean isNull()
           {
                return month.equals(" ") && day.equals(" ") && 
                     year.equals(" ");
           }
      }
      
      import java.io.*;
      import java.util.*;
      
      class SortDates
      {
           public static void main(String[] args)
           {
                Scanner keyboard = new Scanner (System.in);
                System.out.println("Please enter in the file name.");
                String fileName = keyboard.next();
                Date date = new Date();
                PriorityQueue queue = new PriorityQueue():
                BufferedReader reader = new BufferedReader(new FileReader
                     (fileName));
      
                date.input(reader);
                while (!date.isNull())
                {
                     queue.enqueue(date);
                     date = new Date();
                     date.input(reader);
                }
                System.out.println("The names in descending order are: "):
                while (!queue.isEmpty())
                {
                     date = (Date)queue.dequeue();
                     date.output(System.out);
                }
           }
      }
      My last class is supposed to implement PriorityQueueInterface, I don't have much for it. I wrote the last two codes, but this last one I'm just having problems figuring out exactly how to implement a LinkedList. Do I need other classes? What instance variables do I use? Do I need a Node class???
      class PriorityQueue implements PriorityQueueInterface
      {
           private Comparable node;
           private int data;                              // not sure about this! 
           public PriorityQueue(Comparable node, int data)
           {
                this.node = node;
                this.data = data;
           }
           public void enqueue(Comparable key)
           {
                // ??????
           }
           public void dequeue()
           {
                // ??????
           }
      Obviously I need to maintain the linkedlist in sorted order, descending order.

      Please, anyone, just a nudge in the right direction! Where to start?How to test???

      Thanks!
        • 1. Re: Priority Queue as a LinkedList
          791266
          Do you have to implement the linked list? Your PriorityQueue should aggregate a linked list. (Have an instance variable which is a linked list)

          Kaj
          • 2. Re: Priority Queue as a LinkedList
            807599
            I have to implement a PriorityQueue using a LinkedList maintaining that list in descending order. So basically, I just need to define the enqueue to place the months in sorted order correct? The only output is needed are the first 3 letters of the months, however I noticed I made a mistake in the code. The file read in is in this format : 03/16/2009, so I need to convert the month.

            I believe I have everything else in place, I just need to work on the enqueue method. The dequeue and isEmpty methods are straightforward. Am I on the right track? If so, I'm just going to plug away until I get it right! :-)
            • 3. Re: Priority Queue as a LinkedList
              EJP
              This sounds bizarre. The universal technique for implementing a PriorityQueue is an array, in fact the algorithm practically demands it.

              Are you sure you have your requirement straight?
              • 4. Re: Priority Queue as a LinkedList
                807599
                I know. That's why I'm having problems. No array or heaps. Just a LinkedList. Any ideas?
                • 5. Re: Priority Queue as a LinkedList
                  EJP
                  Only that that is not what's generally meant by a PriorityQueue, at least in Java. The requirement seems to be just for a sorted linked list. This also goes against what LinkedList means in Java too, i.e. a double-ended queue with operations taking place at the beginning and end only.

                  And what exactly is PriorityQueueInterface? It's not in the JDK.

                  I would query all this with whoever specified the problem. To say the least, everything is very poorly named w.r.t. the conventions that already exist in the JDK and the Collections API.
                  • 6. Re: Priority Queue as a LinkedList
                    807599
                    Here is the interface that was defined:
                    interface PriorityQueueInterface
                    {
                         boolean isEmpty();
                    
                         void enqueue (Comparable key) throws FullQueue;
                    
                         Comparable dequeue() throws EmptyQueue;
                    }
                    Does this shed some light? I'm assuming the enqueue method should search for the correct place to insert the key, however as you said this goes against the convention of a LinkedList. Any more help would be greatly appreciated. I can always just plug away and hope something good happens, that's what I generally do anyway!
                    • 7. Re: Priority Queue as a LinkedList
                      EJP
                      Well OK I would just go ahead and define a PriorityQueue class using a LinkedList internally, and implement enqueue() as you describe.