public class LinkedListBasedQueue <Item> {
  
  private class Node {
    Item value;
    Node next;
    Node (Item theValue, Node theNext) {
      value = theValue;
      next = theNext;
    }
  }
  
  Node head = null; // head of the queue, which is the first node of the linked list
  Node tail = null; // tail of the queue, which is the last node of the linked list
  
  boolean isEmpty () {
    return (head == null);
  }
  
  void enQ (Item value) {
    if (tail == null) // the queue is empty
      head = tail = new Node (value, null);
    else {
      tail.next = new Node(value, null);
      tail = tail.next;
    }
  }
  
  Item deQ () {
    Item ret = head.value;
    head = head.next;
    if (head == null) // dequeued down to nothing
      tail = null;
    return ret;
  }
}