public class LinkedListBasedQueueWithHeaderNode <Item> {
  
  private class Node {
    Item value;
    Node next;
    Node (Item theValue, Node theNext) {
      value = theValue;
      next = theNext;
    }
  }
 
  Node head; // head of the queue, which is the first node of the linked list
  Node tail; // tail of the queue, which is the last node of the linked list
  
  LinkedListBasedQueueWithHeaderNode() {
    head = tail = new Node (null, null);
  }
  
  
  boolean isEmpty () {
    return (head.next == null);
  }
  
  void enQ (Item value) {
    tail.next = new Node(value, null);
    tail = tail.next;
  }
  
  Item deQ () {
    Item ret = head.next.value;
    head.next = head.next.next; // dummy header node's next should point to the follower of whomever was dequeued
    return ret;
  }
}