Coder Wiki | HowTos | Priority Queue

[Get Code]
PriorityQueue.java
/**
 * Klasse einer prioritaets-Warteschlange
 */
public class ListPriorityQueue {
 
        Node head, tail;
 
        /**
         * Klasse von Knoten fuer eine double-Linked-Queue
         */
        private class Node implements Comparable {
                Node next, prev;
                int data;
 
                /**
                 * Vergleicht den Inhalt zweier Knoten
                 * @param o Object (Hier:Integer)
                 * @return int
                 */
                public int compareTo(Object o) {
                        if (this.data > (Integer) o)
                                return 1;
                        else if (this.data < (Integer) o)
                                return -1;
                        else
                                return 0;
                }
        }
 
        /**
         * Konstruktor
         */
        public ListPriorityQueue() {
                this.head = new Node();
                this.tail = new Node();
 
                head.prev = tail;
                head.next = null;
                tail.prev = null;
                tail.next = head;
        }
 
        /**
         * fuegt, abhaengig von der Groesse des Inhalts, neuen Knoten in die
         * Schlange ein.
         * 
         * @param i int
         */
        public void enter(int i) {
                // erzeugt neuen Knoten
                Node n = new Node();
                n.data = i;
                Node search = tail;
 
                // sucht richtige Stelle zum einfuegen, abhaengig von prioritaet
                while (search.next.next != null) {
                        if (search.next.data > i)
                                break;
                        else
                                search = search.next;
                }
 
                // fuegt an richtiger Stelle den Knoten ein
                n.next = search.next;
                n.prev = search;
                search.next.prev = n;
                search.next = n;
        }
 
        /**
         * entfernt Knoten am head
         */
        public void leave() throws QueueException {
                if (tail.next.next == null)
                        throw new QueueException("PriorityQueue empty!");
                else {
                        head.prev.prev.next = head;
                        head.prev = head.prev.prev;
                }
        }
 
        /**
         * gibt Wert des ersten Knotes am head zurueck
         */
        public int front() throws QueueException {
                return head.prev.data;
        }
 
        /**
         * prueft, ob Queue leer ist
         */
        public boolean is_empty() {
                return tail.next.next == null;
        }
}
Coder How To's

Priority Queue
