The LinkedQueue Class

Here is the class, with its node, fields, and constructor:

public class LinkedQueue<T> implements Queue<T> {

  private Node<T> head;  // the front of the queue, or null when empty
  private Node<T> tail;  // the back of the queue, or null when empty

  private static class Node<T> {
    T value;
    Node<T> next;

    Node(T value) {
      this.value = value;
    }
  }

  public LinkedQueue() {
    head = null;  // the queue starts empty
    tail = null;
  }

  // ... the operations will go here
}

The Node class is the same one we used in LinkedStack. The two references describe the same linked list, so they have to agree with each other. When the queue is empty, both are null. When the queue has one item, both point at the same node. Otherwise tail is the last node of the list that starts at head. Every operation we write has to keep head and tail consistent.

The isEmpty operation only needs one of the two references:

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

Checking tail == null would work just as well.