public class MyDeque implements Deque {
  DLNode header, trailer;  // sentinels
  int size;    // number of elements
  public MyDeque() {  // 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;
  }