Friday, February 6, 2009

Guest Lecture on Queues by John Paxton

public class Driver
{
    public static void main (String  [] args)
    {
        Queue q = new Queue();
        q.enqueue(1);
        q.enqueue(2);
        q.printQueue();
        q.dequeue();
        q.printQueue();
        q.dequeue();
        q.printQueue();
        q.dequeue();
        q.printQueue();
    }
}


public class Node
{
    Node (int contents)
    {
        this.contents = contents;
        this.next = null;
    }
    
    public Node getNext ()
    {
        return next;
    }
    
    public int getContents()
    {
        return contents;
    }
    
    public void setNext (Node n)
    {
        this.next = n;
    }
    
    private int contents;
    private Node next;
}

public class Queue
{
    Queue()
    {
        makeEmpty();
    }
    
    public void makeEmpty()
    {
        first = new Node(-777);
        first.setNext(first);
        last = first;
    }
    
    public void enqueue (int contents)
    {
        Node n = new Node(contents);
        last.setNext(n);
        n.setNext(first);
        last = n;
    }
    
    public void printQueue()
    {
        System.out.println("Queue Contents");
        System.out.println("--------------");
        System.out.print(this);
        System.out.println("---- End -----");
    }
    
    public String toString ()
    {
        String result = "";
        Node pointer = first.getNext();
        while (pointer != first)
        {
            result += pointer.getContents() + "\n";
            pointer = pointer.getNext();
        }
        return result;
    }
    
    public void dequeue ()
    {
        first.setNext(first.getNext().getNext());
        if (first == first.getNext())
        {
            last = first;
        }
    }
    
    private Node first;
    private Node last;
}