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

    public boolean isEmpty() {
    return list.isEmpty();
    }
    
    public void 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);
	if (j == null) {
	      list.setFirst(newNode);
	} else {
	      j.setNext(newNode);
	}
	newNode.setNext(i);
    }



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

// This is a second implementation of Linked Lists.
// It makes sure that the list is in the consistent state 
// when elements are added to it. 

public class LinkedList {
    private Node first;

    public LinkedList() {
        first = null;
    }

    public boolean isEmpty() {
        return (first == null);
    }

    public Node getFirst() {
        return first;
    }

    // allows to set the first node to null
    public void setFirst(Node n) {
        if (n == null) {
            first = null;
        } else {
	     Node newFirst = new Node(n.getData());
	     newFirst.setNext(null); // this is the only element on the list
	     first = newFirst;
	}
		    
    }

    public void addFront(Node n) {
        if (n == null) {
	     System.out.println("addFront: can't add a null reference");
	     System.exit(0);
	}
	Node internal = new Node(n.getData());
    	internal.setNext(first);
    	first = internal;
    }

    public void removeFront() {
        if (first == null) {
	     System.out.println("removeFront: no element to remove");
	     System.exit(0);
	}
	first = first.getNext();
    }
}

public class Node {
    private int data;
    private Node next;

    public Node(int d) {
        data = d;
	next = null; // can skip this line: null is the default value
    }

    public int getData() {
        return data;
    }

    // return the next node
    public Node getNext() {
        return next;
    }

    // set the node 
    public void setNext(Node n) {
        next = n;
    }
}