网络异常，图片无法展示
|
「这是我参与11月更文挑战的第24天，活动详情查看：2021最后一次更文挑战」
设计实现双端队列。
你的实现需要支持以下操作：
- MyCircularDeque(k)：构造函数,双端队列的大小为k。
- insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
- insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
- deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
- deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
- getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
- getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
- isEmpty()：检查双端队列是否为空。
- isFull()：检查双端队列是否满了。
示例：
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3 circularDeque.insertLast(1); // 返回 true circularDeque.insertLast(2); // 返回 true circularDeque.insertFront(3); // 返回 true circularDeque.insertFront(4); // 已经满了，返回 false circularDeque.getRear(); // 返回 2 circularDeque.isFull(); // 返回 true circularDeque.deleteLast(); // 返回 true circularDeque.insertFront(4); // 返回 true circularDeque.getFront(); // 返回 4 复制代码
提示：
- 所有值的范围为 [1, 1000]
- 操作次数的范围为 [1, 1000]
- 请不要使用内置的双端队列库。
本题只是在上文题目《leetcode-622-设计循环队列》的基础上加了一丢丢🤏的难度
首先我们回顾一下循环队列的性质
循环队列其实就像是一个有固定座位数量的餐桌，来吃饭的人依次坐好，当坐满人之后，新来的人坐不下只能离开或者在一旁排队
当先来的人吃饱离开后，此时空出座位，后续的人就可以坐下吃饭了（这里严格遵循先到先吃饱离开的规则😃）
过程如下：
网络异常，图片无法展示
|
那么双端队列依然类似于一个有固定座位数量的餐桌，只不过和循环队列稍有不同。
依然以餐桌为例：
网络异常，图片无法展示
|
理解了循环双端队列的性质后，如何设计该数据结构呢？
思路如下：
- 首先构造函数中，根据传入值记录队列长度
max。接下来创建空数组queue存储队列中的值，并创建head、end指针初初始化指向-1,创建size属性初始化为0 - 队首插入操作中，判断队列是否已满，如果队列已满，返回false。否则判断
head===-1,如果为真，说明队列是初始化状态，此时新插入的值一定在下标0位置，将head = 0 end = 0。否则需要让head指针向前走一步，这里要判断head指针是否在下标0位置，如果在下标0位置，则需要将head指针调整到数组末尾。最后将value插入到head指针所在位置即可，this.size++ - 队尾插入操作中，判断队列是否已满，如果队列已满，返回false。否则判断
end===-1,如果为真，说明队列是初始化状态，此时新插入的值一定在下标0位置，将head = 0 end = 0。否则需要让end指针向后走一步，这里要判断end指针是否在数组末尾位置，如果在数组末尾位置，则需要将end指针调整到下标0位置。最后将value插入到end指针所在位置即可，this.size++ - 删除队首元素操作首先需要判断队列是否为空，如果为空，返回
false。否则只需要调整head指针向后走一步即可。同样需要判断此时head指针是否在数组末尾，如果是，则head = 0。最后不要忘记this.size--
5.删除队尾元素操作首先需要判断队列是否为空，如果为空，返回 false。否则只需要
调整 end 指针向前走一步即可。这里需要判断 end 指针是否在下标 0 位置，如果是，需要将 end 指针调整到数组末尾。最后不要忘记 this.size-- 6. 获取队首元素首先判断队列是否为空，如果为空，返回 -1，否则返回 this.queue[this.head] 即可 7. 获取队尾元素首先判断队列是否为空，如果为空，返回 -1，否则返回
this.queue[this.end] 即可 8. 判断队列是否为空只需要判断 this.size === 0 即可 9. 判断队列是否已满只需要判断 this.size === this.max 即可
以本题示例为例，以上过程如下：
网络异常，图片无法展示
|
代码如下：
var MyCircularDeque = function(k) { this.max = k; this.queue = []; this.head = -1; this.end = -1; this.size = 0; }; /** * @param {number} value * @return {boolean} */ MyCircularDeque.prototype.insertFront = function(value) { if(this.isFull()) return false; if(this.head===-1){ this.head = 0; this.end = 0; }else if(this.head === 0){ this.head = this.max-1 }else{ this.head-- } this.size++; this.queue[this.head] = value; return true; }; /** * @param {number} value * @return {boolean} */ MyCircularDeque.prototype.insertLast = function(value) { if(this.isFull()) return false; if(this.end===-1){ this.head = 0; this.end = 0; }else if(this.end === this.max-1){ this.end = 0 }else{ this.end++ } this.size++; this.queue[this.end] = value; return true; }; /** * @return {boolean} */ MyCircularDeque.prototype.deleteFront = function() { if(this.isEmpty()) return false; if(this.head === this.max-1){ this.head = 0 }else{ this.head++ } this.size--; return true; }; /** * @return {boolean} */ MyCircularDeque.prototype.deleteLast = function() { if(this.isEmpty()) return false; if(this.end === 0){ this.end = this.max-1; }else{ this.end--; } this.size--; return true; }; /** * @return {number} */ MyCircularDeque.prototype.getFront = function() { if(this.isEmpty()) return -1; return this.queue[this.head] }; /** * @return {number} */ MyCircularDeque.prototype.getRear = function() { if(this.isEmpty()) return -1; return this.queue[this.end] }; /** * @return {boolean} */ MyCircularDeque.prototype.isEmpty = function() { return this.size === 0 }; /** * @return {boolean} */ MyCircularDeque.prototype.isFull = function() { return this.size === this.max }; 复制代码
至此我们就完成了 leetcode-641-设计循环双端队列
如有任何问题或建议，欢迎留言讨论！
