/**
 * @auther zhangxufeng@uworks.cc 2016/05/10
 */
public class Queue<AnyType> {
  private static class QueueNode<AnyType> {
    QueueNode() {}
    QueueNode(AnyType e, QueueNode<AnyType> p, QueueNode<AnyType> n) {
      element = e;
      prev = p;
      next = n;
    }

    AnyType element;
    QueueNode<AnyType> prev;
    QueueNode<AnyType> next;
  }

  private QueueNode<AnyType> front;
  private QueueNode<AnyType> rear;
  private int size;

  public Queue() {
    front = new QueueNode<>();
    rear = new QueueNode<>(null, front, null);
    front.next = rear;
    size = 0;
  }

  public int size() {
    return size;
  }

  public boolean isEmpty() {
    return size == 0;
  }

  public void clear() {
    front.next = rear;
    rear.prev = front;
  }

  public void enQueue(AnyType item) {
    rear.prev.next = new QueueNode<>(item, rear.prev, rear);
    rear.prev = rear.prev.next;
    size++;
  }

  public AnyType deQueue() {
    if (isEmpty()) {
      throw new IllegalStateException();
    }

    AnyType result = front.next.element;
    front.next.next.prev = front;
    front.next = front.next.next;
    size--;
    return result;
  }
}