写点什么

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

用户头像
Lee Chen
关注
发布于: 2021 年 04 月 23 日
LeetCode题解:641. 设计循环双端队列,使用数组,JavaScript,详细注释

原题链接:641. 设计循环双端队列


解题思路:


如果你看到这题的时候,感到没有思路,可以先尝试其前导题目:622. 设计循环队列,以及我的题解LeetCode题解:622. 设计循环队列,使用数组,JavaScript,详细注释


创建数组:


  1. 先按照队列的容量,创建相应长度的数组,所有元素都默认为-1。这样获得元素时,只要直接返回即可。

  2. 使用 head 指针,指向队首元素。使用 tail 指针,指向将要从队尾插入元素的位置,及队尾+1。


插入元素:


  1. 从头部添加元素时,先将 head 指针向前移动一位,再将元素插入。从头部移除元素的操作相反。

  2. 从尾部添加元素时,先将元素插入到 tail 指针的位置,再将 tail 指针向后移动一位。从尾部移除元素的操作相反。


判断队列为空或已满:


  1. 如果不断添加元素,最终 head 指针和 tail 指针会相遇,此时由于 tail 指针的位置已有 head 对应的值占据,则队列已满。

  2. 如果不断删除元素,最终 head 指针和 tail 指针会相遇,此时它们指向的位置都为-1,则队列为空。


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


["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 */var MyCircularDeque = function (k) {  // 队列的容量  this.capacity = k;  // 使用数组存放队列元素,所有的初始值都是-1,取值的时候直接返回  this.queue = new Array(k).fill(-1);  // 队列的头指针,即队列头元素的位置  this.head = 0;  // 队列的尾指针,即尾部要插入元素的位置,也就是队列的尾元素的位置+1  this.tail = 0;};
// 将index-1,需要考虑index到达数组首尾时需要循环MyCircularDeque.prototype.reduceIndex = function (index) { return (index + this.capacity - 1) % this.capacity;};
// 将index+1,需要考虑index到达数组首尾时需要循环MyCircularDeque.prototype.addIndex = function (index) { return (index + 1) % this.capacity;};
/** * 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; }
// 从头部插入元素时,要先将头指针向前移动一位 this.head = this.reduceIndex(this.head); // 在新的头指针位置插入元素 this.queue[this.head] = value;
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.queue[this.tail] = value; // 将尾指针向后移动一位,指向下一次插入元素的位置 this.tail = this.addIndex(this.tail);
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; }
// 将头指针的值置为-1,表示元素被删除 this.queue[this.head] = -1; // 删除元素后,要将头指针向后移动一位 this.head = this.addIndex(this.head);
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; }
// 先将尾指针向前移动一位,指向队尾元素 this.tail = this.reduceIndex(this.tail); // 将队尾元素设置为-1 this.queue[this.tail] = -1;
return true;};
/** * Get the front item from the deque. * @return {number} */MyCircularDeque.prototype.getFront = function () { // 直接返回头指针的元素即可,由于初始值是-1,因此如果队列为空,会返回-1 return this.queue[this.head];};
/** * Get the last item from the deque. * @return {number} */MyCircularDeque.prototype.getRear = function () { // 直接返回尾指针-1的元素即可,由于初始值是-1,因此如果队列为空,会返回-1 return this.queue[this.reduceIndex(this.tail)];};
/** * Checks whether the circular deque is empty or not. * @return {boolean} */MyCircularDeque.prototype.isEmpty = function () { // 如果头尾指针的位置相同,且对应位置的值为-1,表示队列中已无元素,则为空 return this.head === this.tail && this.queue[this.head] < 0;};
/** * Checks whether the circular deque is full or not. * @return {boolean} */MyCircularDeque.prototype.isFull = function () { // 如果头尾指针的位置相同,且对应位置的值不为-1,此时无法再插入元素,则队列已满 return this.head === this.tail && this.queue[this.head] >= 0;};
复制代码


发布于: 2021 年 04 月 23 日阅读数: 10
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

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