循环数组和双向链表 2 数据结构，求解《641. 设计循环双端队列》

var MyCircularDeque = function(k) {
  this.ar = new Uint16Array(k + 1)
  this.head = this.rear = 0
  this.size = k + 1
};

MyCircularDeque.prototype.insertFront = function(value) {
  if (this.isFull()) return false
  this.head = (this.head - 1 + this.size) % this.size
  this.ar[this.head] = value
  return true
};

MyCircularDeque.prototype.insertLast = function(value) {
  if (this.isFull()) return false
  this.ar[this.rear] = value
  this.rear = (this.rear + 1) % this.size
  return true
};

MyCircularDeque.prototype.deleteFront = function() {
  if (this.isEmpty()) return false
  this.head = (this.head + 1) % this.size
  return true
};

MyCircularDeque.prototype.deleteLast = function() {
  if (this.isEmpty()) return false
  this.rear = (this.rear - 1 + this.size) % this.size
  return true
};

MyCircularDeque.prototype.getFront = function() {
  if (this.isEmpty()) return -1
  return this.ar[this.head]
};

MyCircularDeque.prototype.getRear = function() {
  if (this.isEmpty()) return -1
  return this.ar[(this.rear - 1 + this.size) % this.size]
};

MyCircularDeque.prototype.isEmpty = function() {
  return this.head === this.rear
};

MyCircularDeque.prototype.isFull = function() {
  return (this.rear + 1) % this.size === this.head
};

class MyCircularDeque {
  ar:number[]
  size: number
  head: number
  rear: number
  constructor(k: number) {
    this.ar = new Array(k + 1).fill(0)
    this.size = k + 1
    this.head = 0
    this.rear = 0
  }

  insertFront(value: number): boolean {
    if (this.isFull()) return false
    this.head = (this.head - 1 + this.size) % this.size
    this.ar[this.head] = value
    return true
  }

  insertLast(value: number): boolean {
    if (this.isFull()) return false
    this.ar[this.rear] = value
    this.rear = (this.rear + 1) % this.size
    return true
  }

  deleteFront(): boolean {
    if (this.isEmpty()) return false
    this.head = (this.head + 1) % this.size
    return true
  }

  deleteLast(): boolean {
    if (this.isEmpty()) return false
    this.rear = (this.rear - 1 + this.size) % this.size
    return true
  }

  getFront(): number {
    if (this.isEmpty()) return -1
    return this.ar[this.head]
  }

  getRear(): number {
    if (this.isEmpty()) return -1
    return this.ar[(this.rear - 1 + this.size) % this.size]
  }

  isEmpty(): boolean {
    return this.head === this.rear
  }

  isFull(): boolean {
    return (this.rear + 1) % this.size === this.head
  }
}

class MyCircularDeque {
  function __construct($k) {
    $this->size = $k + 1;
    $this->ar = array_fill(0, $this->size, 0);
    $this->head = $this->rear = 0;
  }

  function insertFront($value) {
    if ($this->isFull()) return false;
    $this->head = ($this->head - 1 + $this->size) % $this->size;
    $this->ar[$this->head] = $value;
    return true;
  }

  function insertLast($value) {
    if ($this->isFull()) return false;
    $this->ar[$this->rear] = $value;
    $this->rear = ($this->rear + 1) % $this->size;
    return true;
  }

  function deleteFront() {
    if ($this->isEmpty()) return false;
    $this->head = ($this->head + 1) % $this->size;
    return true;
  }

  function deleteLast() {
    if ($this->isEmpty()) return false;
    $this->rear = ($this->rear - 1 + $this->size) % $this->size;
    return true;
  }

  function getFront() {
    if ($this->isEmpty()) return -1;
    return $this->ar[$this->head];
  }

  function getRear() {
    if ($this->isEmpty()) return -1;
    return $this->ar[($this->rear - 1 + $this->size) % $this->size]; 
  }

  function isEmpty() {
    return $this->head === $this->rear;
  }

  function isFull() {
    return ($this->rear + 1) % $this->size === $this->head;
  }
}

type MyCircularDeque struct {
  ar []int
  size int
  head int
  rear int
}

func Constructor(k int) MyCircularDeque {
  return MyCircularDeque {
    make([]int, k + 1),
    k + 1,
    0,
    0,
  }
}

func (this *MyCircularDeque) InsertFront(value int) bool {
  if this.IsFull() {
    return false
  }
  this.head = (this.head - 1 + this.size) % this.size
  this.ar[this.head] = value
  return true
}

func (this *MyCircularDeque) InsertLast(value int) bool {
  if this.IsFull() {
    return false
  }
  this.ar[this.rear] = value
  this.rear = (this.rear + 1) % this.size
  return true
}

func (this *MyCircularDeque) DeleteFront() bool {
  if this.IsEmpty() {
    return false
  }
  this.head = (this.head + 1) % this.size
  return true
}

func (this *MyCircularDeque) DeleteLast() bool {
  if this.IsEmpty() {
    return false
  }
  this.rear = (this.rear - 1 + this.size) % this.size
  return true
}

func (this *MyCircularDeque) GetFront() int {
  if this.IsEmpty() {
    return -1
  }
  return this.ar[this.head]
}

func (this *MyCircularDeque) GetRear() int {
  if this.IsEmpty() {
    return -1
  }
  return this.ar[(this.rear - 1 + this.size) % this.size]
}

func (this *MyCircularDeque) IsEmpty() bool {
  return this.head == this.rear
}

func (this *MyCircularDeque) IsFull() bool {
  return (this.rear + 1) % this.size == this.head
}

class MyCircularDeque {
  private int[] ar;
  private int size;
  private int head;
  private int rear;
  public MyCircularDeque(int k) {
    ar = new int[k + 1];
    size = k + 1;
    head = rear = 0;
  }

  public boolean insertFront(int value) {
    if (isFull()) return false;
    head = (head - 1 + size) % size;
    ar[head] = value;
    return true;
  }

  public boolean insertLast(int value) {
    if (isFull()) return false;
    ar[rear] = value;
    rear = (rear + 1) % size;
    return true;
  }

  public boolean deleteFront() {
    if (isEmpty()) return false;
    head = (head + 1) % size;
    return true;
  }

  public boolean deleteLast() {
    if (isEmpty()) return false;
    rear = (rear - 1 + size) % size;
    return true;
  }

  public int getFront() {
    if (isEmpty()) return -1;
    return ar[head];
  }

  public int getRear() {
    if (isEmpty()) return -1;
    return ar[(rear - 1 + size) % size];
  }

  public boolean isEmpty() {
    return head == rear;
  }

  public boolean isFull() {
    return (rear + 1) % size == head;
  }
}

public class MyCircularDeque {
  private int[] ar;
  private int size;
  private int head;
  private int rear;
  public MyCircularDeque(int k) {
    ar = new int[k + 1];
    size = k + 1;
    head = rear = 0;
  }

  public bool InsertFront(int value) {
    if (IsFull()) return false;
    head =  (head - 1 + size) % size;
    ar[head] = value;
    return true;
  }

  public bool InsertLast(int value) {
    if (IsFull()) return false;
    ar[rear] = value;
    rear = (rear + 1) % size;
    return true;
  }

  public bool DeleteFront() {
    if (IsEmpty()) return false;
    head = (head + 1) % size;
    return true;
  }

  public bool DeleteLast() {
    if (IsEmpty()) return false;
    rear = (rear - 1 + size) % size;
    return true;
  }

  public int GetFront() {
    if (IsEmpty()) return -1;
    return ar[head];
  }

  public int GetRear() {
    if (IsEmpty()) return -1;
    return ar[(rear - 1 + size) % size];
  }

  public bool IsEmpty() {
    return head == rear;
  }

  public bool IsFull() {
    return (rear + 1) % size == head;
  }
}

typedef struct {
  int* ar;
  int size;
  int head;
  int rear;
} MyCircularDeque;

MyCircularDeque* myCircularDequeCreate(int k) {
  MyCircularDeque* obj = malloc(sizeof(MyCircularDeque));
  obj->ar = malloc(sizeof(int) * (k + 1));
  obj->size = k + 1;
  obj->head = obj->rear = 0;
  return obj;
}

bool myCircularDequeIsEmpty(MyCircularDeque* obj) {
  return obj->head == obj->rear;
}

bool myCircularDequeIsFull(MyCircularDeque* obj) {
  return (obj->rear + 1) % obj->size == obj->head;
}

bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
  if (myCircularDequeIsFull(obj)) return false;
  obj->head = (obj->head - 1 + obj->size) % obj->size;
  obj->ar[obj->head] = value;
  return true;
}

bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) {
  if (myCircularDequeIsFull(obj)) return false;
  obj->ar[obj->rear] = value;
  obj->rear = (obj->rear + 1) % obj->size;
  return true;
}

bool myCircularDequeDeleteFront(MyCircularDeque* obj) {
  if (myCircularDequeIsEmpty(obj)) return false;
  obj->head = (obj->head + 1) % obj->size;
  return true;
}

bool myCircularDequeDeleteLast(MyCircularDeque* obj) {
  if (myCircularDequeIsEmpty(obj)) return false;
  obj->rear = (obj->rear - 1 + obj->size) % obj->size;
  return true;
}

int myCircularDequeGetFront(MyCircularDeque* obj) {
  if (myCircularDequeIsEmpty(obj)) return -1;
  return obj->ar[obj->head];
}

int myCircularDequeGetRear(MyCircularDeque* obj) {
  if (myCircularDequeIsEmpty(obj)) return -1;
  return obj->ar[(obj->rear - 1 + obj->size) % obj->size];
}

void myCircularDequeFree(MyCircularDeque* obj) {
  free(obj->ar);
  free(obj);
}

class MyCircularDeque {
private:
  vector<int> ar;
  int size;
  int head;
  int rear;
public:
  MyCircularDeque(int k) {
    ar = vector<int>(k + 1);
    size = k + 1;
    head = rear = 0;
  }

  bool insertFront(int value) {
    if (isFull()) return false;
    head = (head - 1 + size) % size;
    ar[head] = value;
    return true;
  }

  bool insertLast(int value) {
    if (isFull()) return false;
    ar[rear] = value;
    rear = (rear + 1) % size;
    return true;
  }

  bool deleteFront() {
    if (isEmpty()) return false;
    head = (head + 1) % size;
    return true;
  }

  bool deleteLast() {
    if (isEmpty()) return false;
    rear = (rear - 1 + size) % size;
    return true;
  }

  int getFront() {
    if (isEmpty()) return -1;
    return ar[head];
  }

  int getRear() {
    if (isEmpty()) return -1;
    return ar[(rear - 1 + size) % size];
  }

  bool isEmpty() {
    return head == rear;
  }

  bool isFull() {
    return (rear + 1) % size == head;
  }
};

class MyCircularDeque:
  def __init__(self, k: int):
    self.size, self.head, self.rear = k + 1, 0, 0
    self.ar = [0] * self.size

  def insertFront(self, value: int) -> bool:
    if self.isFull(): return False
    self.head = (self.head - 1 + self.size) % self.size
    self.ar[self.head] = value
    return True

  def insertLast(self, value: int) -> bool:
    if self.isFull(): return False
    self.ar[self.rear] = value
    self.rear = (self.rear + 1) % self.size
    return True

  def deleteFront(self) -> bool:
    if self.isEmpty(): return False
    self.head = (self.head + 1) % self.size
    return True

  def deleteLast(self) -> bool:
    if self.isEmpty(): return False
    self.rear = (self.rear - 1 + self.size) % self.size
    return True

  def getFront(self) -> int:
    if self.isEmpty(): return -1
    return self.ar[self.head]

  def getRear(self) -> int:
    if self.isEmpty(): return -1
    return self.ar[(self.rear - 1 + self.size) % self.size]

  def isEmpty(self) -> bool:
    return self.head == self.rear

  def isFull(self) -> bool:
    return (self.rear + 1) % self.size == self.head

class DoubleListNode {
  constructor(val, next = null, prev = null) {
    this.val = val
    this.next = next
    this.prev = prev
  }
}

var MyCircularDeque = function(k) {
  this.capacity = k
  this.size = 0
  this.head = null
  this.tail = null
};

MyCircularDeque.prototype.insertFront = function(value) {
  if (this.isFull()) return false
  const n = new DoubleListNode(value, null, null)
  if (this.isEmpty()) {
    this.head = this.tail = n
  } else {
    n.next = this.head
    this.head = this.head.prev = n
  }
  this.size++
  return true
};

MyCircularDeque.prototype.insertLast = function(value) {
  if (this.isFull()) return false
  const n = new DoubleListNode(value, null, null)
  if (this.isEmpty()) {
    this.head = this.tail = n
  } else {
    n.prev = this.tail
    this.tail = this.tail.next = n
  }
  this.size++
  return true
};

MyCircularDeque.prototype.deleteFront = function() {
  if (this.isEmpty()) return false
  this.head = this.head.next
  this.size--
  return true
};

MyCircularDeque.prototype.deleteLast = function() {
  if (this.isEmpty()) return false
  this.tail = this.tail.prev
  this.size--
  return true
};

MyCircularDeque.prototype.getFront = function() {
  if (this.isEmpty()) return -1
  return this.head.val
};

MyCircularDeque.prototype.getRear = function() {
  if (this.isEmpty()) return -1
  return this.tail.val
};

MyCircularDeque.prototype.isEmpty = function() {
  return this.size === 0
};

MyCircularDeque.prototype.isFull = function() {
  return this.size === this.capacity
};

class DoubleListNode {
  val: number
  next: DoubleListNode
  prev: DoubleListNode
  constructor (val: number, next: DoubleListNode = null, prev: DoubleListNode = null) {
    this.val = val
    this.next = next
    this.prev = prev
  }
}
class MyCircularDeque {
  head: DoubleListNode = null
  tail: DoubleListNode = null
  size: number = 0
  capacity: number
  constructor(k: number) {
    this.capacity = k
  }

  insertFront(value: number): boolean {
    if (this.isFull()) return false
    const n = new DoubleListNode(value)
    if (this.isEmpty()) {
      this.head = this.tail = n
    } else {
      n.next = this.head
      this.head = this.head.prev = n
    }
    this.size++
    return true
  }

  insertLast(value: number): boolean {
    if (this.isFull()) return false
    const n = new DoubleListNode(value)
    if (this.isEmpty()) {
      this.head= this.tail = n
    } else {
      n.prev = this.tail
      this.tail = this.tail.next = n
    }
    this.size++
    return true
  }

  deleteFront(): boolean {
    if (this.isEmpty()) return false
    this.head = this.head.next
    this.size--
    return true
  }

  deleteLast(): boolean {
    if (this.isEmpty()) return false
    this.tail = this.tail.prev
    this.size--
    return true
  }

  getFront(): number {
    if (this.isEmpty()) return -1
    return this.head.val
  }

  getRear(): number {
    if (this.isEmpty()) return -1
    return this.tail.val
  }

  isEmpty(): boolean {
    return this.size === 0
  }

  isFull(): boolean {
    return this.size === this.capacity
  }
}

class DoubleListNode {
  public $val;
  public $next;
  public $prev;
  function __construct($val, $next = null, $prev = null) {
    $this->val = $val;
    $this->next = $next;
    $this->prev = $prev;
  }
}
class MyCircularDeque {
  private $head = null;
  private $tail = null;
  private $capacity;
  private $size = 0;
  function __construct($k) {
    $this->capacity = $k;
  }

  function insertFront($value) {
    if ($this->isFull()) return false;
    $n = new DoubleListNode($value);
    if ($this->isEmpty()) {
      $this->head = $this->tail = $n;
    } else {
      $n->next = $this->head;
      $this->head = $this->head->prev = $n;
    }
    $this->size++;
    return true;
  }

  function insertLast($value) {
    if ($this->isFull()) return false;
    $n = new DoubleListNode($value);
    if ($this->isEmpty()) {
      $this->head = $this->tail = $n;
    } else {
      $n->prev = $this->tail;
      $this->tail = $this->tail->next = $n;
    }
    $this->size++;
    return true;
  }

  function deleteFront() {
    if ($this->isEmpty()) return false;
    $this->head = $this->head->next;
    $this->size--;
    return true;
  }

  function deleteLast() {
    if ($this->isEmpty()) return false;
    $this->tail = $this->tail->prev;
    $this->size--;
    return true;
  }

  function getFront() {
    if ($this->isEmpty()) return -1;
    return $this->head->val;
  }

  function getRear() {
    if ($this->isEmpty()) return -1;
    return $this->tail->val;
  }

  function isEmpty() {
    return $this->size === 0;
  }

  function isFull() {
    return $this->size === $this->capacity;
  }
}

type DoubleListNode struct {
  val int
  next *DoubleListNode
  prev *DoubleListNode
}

type MyCircularDeque struct {
  capacity int
  size int
  head *DoubleListNode
  tail *DoubleListNode
}

func Constructor(k int) MyCircularDeque {
  return MyCircularDeque{
    k,
    0,
    nil,
    nil,
  }
}

func (this *MyCircularDeque) InsertFront(value int) bool {
  if this.IsFull() {
    return false
  }
  n := &DoubleListNode{value, nil, nil}
  if this.IsEmpty() {
    this.head = n
    this.tail = n
  } else {
    n.next = this.head
    this.head.prev = n
    this.head = n
  }
  this.size++
  return true
}

func (this *MyCircularDeque) InsertLast(value int) bool {
  if this.IsFull() {
    return false
  }
  n := &DoubleListNode{value, nil, nil}
  if this.IsEmpty() {
    this.head = n
    this.tail = n
  } else {
    n.prev = this.tail
    this.tail.next = n
    this.tail = n
  }
  this.size++
  return true
}

func (this *MyCircularDeque) DeleteFront() bool {
  if this.IsEmpty() {
    return false
  }
  this.head = this.head.next
  this.size--
  return true
}

func (this *MyCircularDeque) DeleteLast() bool {
  if this.IsEmpty() {
    return false
  }
  this.tail = this.tail.prev
  this.size--
  return true
}

func (this *MyCircularDeque) GetFront() int {
  if this.IsEmpty() {
    return -1
  }
  return this.head.val
}

func (this *MyCircularDeque) GetRear() int {
  if this.IsEmpty() {
    return -1
  }
  return this.tail.val
}

func (this *MyCircularDeque) IsEmpty() bool {
  return this.size == 0
}

func (this *MyCircularDeque) IsFull() bool {
  return this.size == this.capacity
}

class DoubleListNode {
  public int val;
  public DoubleListNode next;
  public DoubleListNode prev;
  public DoubleListNode(int val, DoubleListNode next, DoubleListNode prev) {
    this.val = val;
    this.next = next;
    this.prev = prev;
  }
}
class MyCircularDeque {
  private int capacity;
  private int size = 0;
  private DoubleListNode head;
  private DoubleListNode tail;
  public MyCircularDeque(int k) {
    capacity = k;
  }

  public boolean insertFront(int value) {
    if (isFull()) return false;
    DoubleListNode n = new DoubleListNode(value, null, null);
    if (isEmpty()) {
      head = tail = n;
    } else {
      n.next = head;
      head = head.prev = n;
    }
    size++;
    return true;
  }

  public boolean insertLast(int value) {
    if (isFull()) return false;
    DoubleListNode n = new DoubleListNode(value, null, null);
    if (isEmpty()) {
      head = tail = n;
    } else {
      n.prev = tail;
      tail = tail.next = n;
    }
    size++;
    return true;
  }

  public boolean deleteFront() {
    if (isEmpty()) return false;
    head = head.next;
    size--;
    return true;
  }

  public boolean deleteLast() {
    if (isEmpty()) return false;
    tail = tail.prev;
    size--;
    return true;
  }

  public int getFront() {
    if (isEmpty()) return -1;
    return head.val;
  }

  public int getRear() {
    if (isEmpty()) return -1;
    return tail.val;
  }

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

  public boolean isFull() {
    return size == capacity;
  }
}

public class DoubleListNode {
  public int val;
  public DoubleListNode next;
  public DoubleListNode prev;
  public DoubleListNode(int val, DoubleListNode next = null, DoubleListNode prev = null) {
    this.val = val;
    this.next = next;
    this.prev = prev;
  }
}
public class MyCircularDeque {
  private int capacity;
  private int size;
  DoubleListNode head;
  DoubleListNode tail;
  public MyCircularDeque(int k) {
    capacity = k;
  }

  public bool InsertFront(int value) {
    if (IsFull()) return false;
    DoubleListNode n = new DoubleListNode(value);
    if (IsEmpty()) {
      head = tail = n;
    } else {
      n.next = head;
      head = head.prev = n;
    }
    size++;
    return true;
  }

  public bool InsertLast(int value) {
    if (IsFull()) return false;
    DoubleListNode n = new DoubleListNode(value);
    if (IsEmpty()) {
      head = tail = n;
    } else {
      n.prev = tail;
      tail = tail.next = n;
    }
    size++;
    return true;
  }

  public bool DeleteFront() {
    if (IsEmpty()) return false;
    head = head.next;
    size--;
    return true;
  }

  public bool DeleteLast() {
    if (IsEmpty()) return false;
    tail = tail.prev;
    size--;
    return true;
  }

  public int GetFront() {
    if (IsEmpty()) return -1;
    return head.val;
  }

  public int GetRear() {
    if (IsEmpty()) return -1;
    return tail.val;
  }

  public bool IsEmpty() {
    return size == 0;
  }

  public bool IsFull() {
    return size == capacity;
  }
}

typedef struct {
  int val;
  struct DoubleListNode* next;
  struct DoubleListNode* prev;
} DoubleListNode;

DoubleListNode* DoubleListNodeCreate(int val) {
  DoubleListNode* obj = malloc(sizeof(DoubleListNode));
  obj->val = val;
  obj->next = NULL;
  obj->prev = NULL;
  return obj;
}

typedef struct {
  int capacity;
  int size;
  DoubleListNode* head;
  DoubleListNode* tail;
} MyCircularDeque;

MyCircularDeque* myCircularDequeCreate(int k) {
  MyCircularDeque* obj = malloc(sizeof(MyCircularDeque));
  obj->capacity = k;
  obj->size = 0;
  obj->head = NULL;
  obj->tail = NULL;
  return obj;
}

bool myCircularDequeIsEmpty(MyCircularDeque* obj) {
  return obj->size == 0;
}

bool myCircularDequeIsFull(MyCircularDeque* obj) {
  return obj->size == obj->capacity;
}

bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
  if (myCircularDequeIsFull(obj)) return false;
  DoubleListNode* n = malloc(sizeof(DoubleListNode));
  n->val = value;
  if (myCircularDequeIsEmpty(obj)) {
    obj->head = obj->tail = n;
  } else {
    n->next = obj->head;
    obj->head = obj->head->prev = n;
  }
  obj->size++;
  return true;
}

bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) {
  if (myCircularDequeIsFull(obj)) return false;
  DoubleListNode* n = malloc(sizeof(DoubleListNode));
  n->val = value;
  if (myCircularDequeIsEmpty(obj)) {
    obj->head = obj->tail = n;
  } else {
    n->prev = obj->tail;
    obj->tail = obj->tail->next = n;
  }
  obj->size++;
  return true;
}

bool myCircularDequeDeleteFront(MyCircularDeque* obj) {
  if (myCircularDequeIsEmpty(obj)) return false;
  obj->head = obj->head->next;
  obj->size--;
  return true;
}

bool myCircularDequeDeleteLast(MyCircularDeque* obj) {
  if (myCircularDequeIsEmpty(obj)) return false;
  obj->tail = obj->tail->prev;
  obj->size--;
  return true;
}

int myCircularDequeGetFront(MyCircularDeque* obj) {
  if (myCircularDequeIsEmpty(obj)) return -1;
  return obj->head->val;
}

int myCircularDequeGetRear(MyCircularDeque* obj) {
  if (myCircularDequeIsEmpty(obj)) return -1;
  return obj->tail->val;
}

void myCircularDequeFree(MyCircularDeque* obj) {
  free(obj->head);
  free(obj->tail);
  free(obj);
}

class DoubleListNode {
public:
  int val;
  DoubleListNode* next;
  DoubleListNode* prev;
  DoubleListNode(int val) {
    this->val = val;
    this->next = nullptr;
    this->prev = nullptr;
  }
};

class MyCircularDeque {
private:
  int capacity;
  int size = 0;
  DoubleListNode* head = nullptr;
  DoubleListNode* tail = nullptr;
public:
  MyCircularDeque(int k) {
    capacity = k;
  }

  bool insertFront(int value) {
    if (isFull()) return false;
    DoubleListNode* n = new DoubleListNode(value);
    if (isEmpty()) {
      head = tail = n;
    } else {
      n->next = head;
      head = head->prev = n;
    }
    size++;
    return true;
  }

  bool insertLast(int value) {
    if (isFull()) return false;
    DoubleListNode* n = new DoubleListNode(value);
    if (isEmpty()) {
      head = tail = n;
    } else {
      n->prev = tail;
      tail = tail->next = n;
    }
    size++;
    return true;
  }

  bool deleteFront() {
    if (isEmpty()) return false;
    head = head->next;
    size--;
    return true;
  }

  bool deleteLast() {
    if (isEmpty()) return false;
    tail = tail->prev;
    size--;
    return true;
  }

  int getFront() {
    if (isEmpty()) return -1;
    return head->val;
  }

  int getRear() {
    if (isEmpty()) return -1;
    return tail->val;
  }

  bool isEmpty() {
    return size == 0;
  }

  bool isFull() {
    return size == capacity;
  }
};

class DoubleListNode:
  def __init__(self, val: int, next = None, prev = None):
    self.val = val
    self.next = next
    self.prev = prev

class MyCircularDeque:
    def __init__(self, k: int):
      self.capacity = k
      self.size = 0
      self.tail = self.head = None

    def insertFront(self, value: int) -> bool:
      if self.isFull(): return False
      n = DoubleListNode(value)
      if self.isEmpty(): 
        self.tail = n
      else:
        n.next = self.head
        self.head.prev = n
      self.head = n
      self.size += 1
      return True

    def insertLast(self, value: int) -> bool:
      if self.isFull(): return False
      n = DoubleListNode(value)
      if self.isEmpty(): 
        self.head = n
      else:
        n.prev = self.tail
        self.tail.next = n
      self.tail = n
      self.size += 1
      return True

    def deleteFront(self) -> bool:
      if self.isEmpty(): return False
      self.head = self.head.next
      self.size -= 1
      return True

    def deleteLast(self) -> bool:
      if self.isEmpty(): return False
      self.tail = self.tail.prev
      self.size -= 1
      return True

    def getFront(self) -> int:
      if self.isEmpty(): return -1
      return self.head.val

    def getRear(self) -> int:
      if self.isEmpty(): return -1
      return self.tail.val

    def isEmpty(self) -> bool:
      return self.size == 0

    def isFull(self) -> bool:
      return self.size == self.capacity