LeetCode题解：641. 设计循环双端队列，使用双向链表，JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/design-circular-deque/

解题思路：

如果你看到这题的时候，感到没有思路，可以先尝试其前导题目：622. 设计循环队列，以及我的题解LeetCode题解：622. 设计循环队列，使用双向链表，JavaScript，详细注释。

1. 使用双向链表，每次插入元素时，都创建一个节点，将其连接到链表的头或尾。
2. 删除元素时，值需要将链表头尾节点的连接打断即可。
3. 使用头尾指针，分别指向链表的头尾，用于取值、添加和删除。
4. 使用length计数，capacity表示最大容量，length等于capacity时，表示链表已满。

在默认用例通过后，可以补充测试如下两个用例，如果都能通过，那么这题基本就没问题了。

["MyCircularDeque","insertFront","getRear","insertFront","getRear","insertLast","getFront","getRear","getFront","insertLast","deleteLast","getFront"]\n[[3],[9],[],[9],[],[5],[],[],[],[8],[],[]]

["MyCircularDeque","insertFront","deleteLast","getRear","getFront","getFront","deleteFront","insertFront","insertLast","insertFront","getFront","insertFront"]\n[[4],[9],[],[],[],[],[],[6],[5],[9],[],[6]]

/**
 * Initialize your data structure here. Set the size of the deque to be k.
 * @param {number} k
 */
function ListNode(value) {
  this.value = value;
  this.prev = this.next = null;
}
var MyCircularDeque = function (k) {
  this.capacity = k; // 储存队列的容量
  this.length = 0; // 储存队列的长度
  const node = this.createNode();
  this.head = node;
  this.tail = node;
};

MyCircularDeque.prototype.createNode = function (value = -1) {
  return new ListNode(value);
};

/**
 * Adds an item at the front of Deque. Return true if the operation is successful.
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertFront = function (value) {
  // 判断队列是否已满
  if (this.isFull()) {
    return false;
  }

  // 创建新节点
  const node = this.createNode(value);
  // 将新节点与队首节点相互连接
  this.head.next = node;
  node.prev = this.head;
  // 将头指针指向新队首节点
  this.head = node;
  // 队列长度+1
  this.length++;

  return true;
};

/**
 * Adds an item at the rear of Deque. Return true if the operation is successful.
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertLast = function (value) {
  // 判断队列是否已满
  if (this.isFull()) {
    return false;
  }

  // 将新值存储在尾指针的节点上
  this.tail.value = value;
  // 创建新节点
  const node = this.createNode();
  // 将新节点与尾指针的节点相互连接
  this.tail.prev = node;
  node.next = this.tail;
  // 尾指针指向新节点
  this.tail = node;
  // 队列长度+1
  this.length++;

  return true;
};

/**
 * Deletes an item from the front of Deque. Return true if the operation is successful.
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteFront = function () {
  // 判断队列是否为空
  if (this.isEmpty()) {
    return false;
  }

  // 缓存队首的上一个元素
  const temp = this.head.prev;
  // 将队首与其上一个元素的连接互相打断
  this.head.prev = null;
  temp.next = null;
  // 将头指针移动到新队首
  this.head = temp;
  // 队列长度-1
  this.length--;

  return true;
};

/**
 * Deletes an item from the rear of Deque. Return true if the operation is successful.
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteLast = function () {
  // 判断队列是否为空
  if (this.isEmpty()) {
    return false;
  }

  // 缓存队尾元素
  const temp = this.tail.next;
  // 将队尾元素的值设为-1，即删除了队尾的值
  temp.value = -1;
  // 将尾指针与队尾节点的连接打断
  this.tail.next = null;
  temp.prev = null;
  // 将尾指针指向新的插入对位元素的节点
  this.tail = temp;
  // 队列长度-1
  this.length--;

  return true;
};

/**
 * Get the front item from the deque.
 * @return {number}
 */
MyCircularDeque.prototype.getFront = function () {
  // 队首的值可直接返回头节点的值
  return this.head.value;
};

/**
 * Get the last item from the deque.
 * @return {number}
 */
MyCircularDeque.prototype.getRear = function () {
  // 如果队列为空，则返回-1
  if (this.isEmpty()) {
    return -1;
  }

  // 如果队列不为空，则返回头对位的值
  return this.tail.next.value;
};

/**
 * Checks whether the circular deque is empty or not.
 * @return {boolean}
 */
MyCircularDeque.prototype.isEmpty = function () {
  return !this.length;
};

/**
 * Checks whether the circular deque is full or not.
 * @return {boolean}
 */
MyCircularDeque.prototype.isFull = function () {
  return this.length === this.capacity;
};