public class NodeDeque implements Deque {
  protected DLNode header, trailer;  // sentinels
  protected int size;    // number of elements
  public NodeDeque() {  // initialize an empty deque
    header = new DLNode();
    trailer = new DLNode();
    header.setNext(trailer);  // make header point to trailer
    trailer.setPrev(header);  // make trailer point to header
    size = 0;
  }