A linked list-based implementation of a queue.

ListBasedQueue.java

public class ListBasedQueue<T> implements Queue<T>
{
    private Node<T> first;      // beginning of queue
    private Node<T> last;       // For efficiency, maintain a reference to the least-recently added Node on the queue.

    public ListBasedQueue() {
        first = null;
        last = null;
    }

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

    public void enqueue(T item) {
        Node<T> x = new Node<T>(item);
        if (isEmpty()) {
            first = x;
            last = x;
        } else {
            last.next = x;
            last = x;
        }
    }

    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        T item = first.data;
        first = first.next;
        if (isEmpty()) {
            last = null;
        }
        return item;
    }

    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return first.data;
    }

    private class Node<T> {
        public T data;
        public Node<T> next;

        public Node(T data) {
            this(data, null);
        }

        public Node(T data, Node<T> n) {
            this.data = data;
            next = n;
        }
    }
    
    public static interface Queue<T> {

        /**
         * Adds an element to the queue
         */
        public void enqueue(T data);

        /**
         * Removes an element from the queue
         */
        public T dequeue();

        /**
         * Takes the most recently added element off of the queue without actually removing it
         */
        public T peek();

        /**
         * Tests if the queue has any elements on it
         */
        public boolean isEmpty();

    }


}