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:

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:

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.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.