`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.

```
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

```
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.