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:
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:
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();
}
}
}
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);
}