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 {

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

public void enqueue(int k) {
if (list.isEmpty()) {
Node m = new Node(k);
}
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.