For this assignment we are considering a linked list implementation of a priority queue. A priority queue is a queue in which dequeue method returns an element with the highest priority (i.e. the largest value of data), regardless of the order in which the elements were inserted. We are building the following implementation of a priority queue:

The elements are stored in an ordered linked list (in decreasing order).
dequeue returns the first element of the queue. This takes O(1) time (i.e. constant time)
enqueue inserts the element into the list according to the ordering (i.e. enqueue method has to traverse the list to find the right position for the element). This takes O(n) time (i.e. linear time).

This is the attempt for enqueue method of a priority queue that we have come up with so far. The problems that we have noticed so far are:

It will not insert an element at the front of the queue.
It doesn't update x at the end of the loop.

If you notice any other problems with it, please make a note, we will continue this discussion on Wednesday. And if you have your own version that you would like to propose, please send it to me, and I'll post it on this page (authors' names withheld).


public class PriorityQueue {
    private LinkedList list = new LinkedList();

    public boolean isEmpty() {
        return list.isEmpty();
    }

    public void enqueue(int k) {
        if (list.isEmpty()) {
            Node m = new Node(k);
            m.addFront();
        }
         Node x = list.getFirst();
          Node y;
          while(x.getData() > k){
               y = x.getNext();
               if(y.getData() =< k){
                    Node z = new Node(k);
                     z.setNext(y);
                      x.setNext(z);
               }
          }
    }

    public int dequeue() {
        if (list.isEmpty()) {
            System.out.println("Queue underflow");
            System.exit(0);
        }
            Node n = list.getFirst();
                list.removeFront();
                    return n.getData();
    }

    // can be used for testing
    public void printQueue() {
        Node n = list.getFirst();
        while (n != null) {
                System.out.println(n.getData());
                    n = n.getNext();
        }
    }
}

You will need the files Node.java and LinkedList.java from the previous lecture in order to compile this file. If you want to test it, you may use the Packages program (replace the IntQueue by PriorityQueue).

Below is another proposal. Read it carefully (pictures help!) and try to figure out whether it works. Then test it and, if it works not the way you expected, explain the results. If you understand what this method does and why, then you are doing really well in this class!


enqueue(int k) {
    Node i = list.getFirst();
    Node j = null;
    while(i != null && i.getData() > k) {
        j = i;
        i = i.getNext();
    }
    Node newNode = new Node(k);
    newNode.setNext(i);
    if (j != null)  j.setNext(newNode);
}

This is an example from CSci 2101 course.