Queue

Intro

First in first out (FIFO)

Interface

public interface CuteQueue<T> {
    // add an item to the end of the list
    public CuteQueue<T> add(T item);
    // remove the first item in the list
    public T remove();
    // check if the queue is empty
    public boolean isEmpty();
}

Linked List Implementation

public class QueueLinkedList<T> implements CuteQueue<T> {
    private class ListNode {
        ListNode next;
        T data;
        ListNode(T data) { this.data = data; }
    }

    ListNode first;
    ListNode last;

    @Override
    public CuteQueue<T> add(T item) {
        if (last == null) {
            last = new ListNode(item);
            first = last;
        } else {
            ListNode previous = last;
            last = new ListNode(item);
            previous.next = last;
        }
        return this;
    }

    @Override
    public T remove() {
        if (first == null)
            throw new NoSuchElementException();
        T val = first.data;
        first = first.next;
        if (first == null)
            last = null;
        return val;
    }

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