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

用户头像
Lee Chen
关注
发布于: 2020 年 09 月 29 日
LeetCode题解:641. 设计循环双端队列,使用双向链表,JavaScript,详细注释

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



解题思路:



如果你看到这题的时候,感到没有思路,可以先尝试其前导题目:622. 设计循环队列,以及我的题解[LeetCode题解:622. 设计循环队列,使用双向链表,JavaScript,详细注释](https://leetcode-cn.com/problems/design-circular-queue/solution/leetcodeti-jie-622-she-ji-xun-huan-dui-lie-shi-y-2/)



  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;
};



发布于: 2020 年 09 月 29 日 阅读数: 19
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:641. 设计循环双端队列,使用双向链表,JavaScript,详细注释