Priority queue implementation.

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


This is a takehome exam 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.