LLQueue.java

Download 
1/*2 * LLQueue.java3 *4 * Computer Science S-22, Harvard University5 */6 7/*8 * A generic class that implements our Queue interface using a linked list.9 */10public class LLQueue<T> implements Queue<T> {11    // Inner class for a node.  We use an inner class so that the LLQueue12    // methods can access the fields of the nodes.13    private class Node {14        private T item;15        private Node next;16        17        private Node(T i, Node n) {18            item = i;19            next = n;20        }21    }22    23    // the fields of the LLQueue object24    private Node front;    // the node containing the item at the front25    private Node rear;     // the node containing the item at the rear26    27    /*28     * Constructs an LLQueue object for a queue that is initially29     * empty.30     */31    public LLQueue() {32        front = null;33        rear = null;34    }35    36    /* 37     * isEmpty - returns true if the queue is empty, and false otherwise38     */39    public boolean isEmpty() {40        return (front == null);41    }42    43    /*44     * isFull - always returns false, because the linked list can45     * grow indefinitely and thus the queue is never full.46     */47    public boolean isFull() {48        return false;49    }50 51    /* 52     * insert - adds the specified item at the rear of the queue.53     * Always returns true, because the linked list is never full.54     */55    public boolean insert(T item) {        56        if (item == null) {57            throw new IllegalArgumentException();58        }59        Node newNode = new Node(item, null);60        61        if (isEmpty()) {62            front = newNode;63            rear = newNode;64        } else {65            rear.next = newNode;66            rear = newNode;67        }                          68        69        return true;70    }71    72    /* 73     * remove - removes the item at the front of the queue and returns a74     * reference to the removed object.  Returns null if the queue is75     * empty.76     */77    public T remove() {78        if (isEmpty()) {79            return null;80        }81        82        T removed = front.item;83        if (front == rear) {       // removing the only item84            front = null;85            rear = null;86        } else {87            front = front.next;88        }89        90        return removed;91    }92    93    /* 94     * peek - returns a reference to the item at the front of the queue95     * without removing it. Returns null if the queue is empty.96     */97    public T peek() {98        if (isEmpty()) {99            return null;100        }101        return front.item;102    }103    104    /*105     * toString - converts the stack into a String of the form 106     * {front, one-after-front, two-after-front, ...}107     */108    public String toString() {109        String str = "{";110        111        Node trav = front;112        while (trav != null) {113            str = str + trav.item;114            if (trav.next != null) {115                str = str + ", ";116            }117            trav = trav.next;118        }119        120        str = str + "}";121        return str;122    }123}