设计循环双端队列

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

设计实现双端队列。

实现 MyCircularDeque 类:

MyCircularDeque(int k)?：构造函数,双端队列最大为 k 。
boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true?，否则返回 false 。
boolean insertLast()?：将一个元素添加到双端队列尾部。如果操作成功返回 true?，否则返回 false 。
boolean deleteFront()?：从双端队列头部删除一个元素。 如果操作成功返回 true?，否则返回 false 。
boolean deleteLast()?：从双端队列尾部删除一个元素。如果操作成功返回 true?，否则返回 false 。
int getFront()?)：从双端队列头部获得一个元素。如果双端队列为空，返回 -1?。
int getRear()?：获得双端队列的最后一个元素。?如果双端队列为空，返回 -1 。
boolean isEmpty()?：若双端队列为空，则返回?true?，否则返回 false ?。
boolean isFull()?：若双端队列满了，则返回?true?，否则返回 false 。

示例 1：

输入
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]

解释
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 <= k <= 1000
• 0 <= value <= 1000
• insertFront,?insertLast,?deleteFront,?deleteLast,?getFront,?getRear,?isEmpty,?isFull? 调用次数不大于?2000?次

思路分析

题目是要我们实现 MyCircularDeque 类，也就是一个双端队列。我们可以先看一下具体要求我们事先的功能，我们总共需要实现8个功能，分别是：

• boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true?，否则返回 false 。
• boolean insertLast()?：将一个元素添加到双端队列尾部。如果操作成功返回 true?，否则返回 false 。
• boolean deleteFront()?：从双端队列头部删除一个元素。 如果操作成功返回 true?，否则返回 false 。
• boolean deleteLast()?：从双端队列尾部删除一个元素。如果操作成功返回 true?，否则返回 false 。
• int getFront()?)：从双端队列头部获得一个元素。如果双端队列为空，返回 -1?。
• int getRear()?：获得双端队列的最后一个元素。?如果双端队列为空，返回 -1 。
• boolean isEmpty()?：若双端队列为空，则返回?true?，否则返回 false ?。
• boolean isFull()?：若双端队列满了，则返回?true?，否则返回 false 。

知道了需求之后，我们发现使用一个数组就可以简单实现这些功能：

• MyCircularDeque(int k)?：构造函数,双端队列最大为 k 。
  首先是构造函数，我们直接使用一个数组来作为数据存储容器，并将最大容量k的数值保存起来。

/**
 * @param {number} k
 */
var MyCircularDeque = function(k) {
    this.size = k;
    this.list = [];
};

• boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true?，否则返回 false 。
  先判断容器是不是已经满了，满了则无法进行插入操作，直接返回false，否则则将元素从头部插入容器，这里可以直接使用数组的unshift方法。

/** 
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertFront = function(value) {
    if(this.list.length == this.size) return false;
    this.list.unshift(value);
    return true;
};

• boolean insertLast()?：将一个元素添加到双端队列尾部。如果操作成功返回 true?，否则返回 false 。
  先判断容器是不是已经满了，满了则无法进行插入操作，直接返回false，否则则将元素从头部插入容器，这里可以直接使用数组的push方法。

/** 
 * @param {number} value
 * @return {boolean}
 */
MyCircularDeque.prototype.insertLast = function(value) {
    if(this.list.length == this.size) return false;
    this.list.push(value);
    return true;
};

• boolean deleteFront()?：从双端队列头部删除一个元素。 如果操作成功返回 true?，否则返回 false 。
  先判断容器是否为空，为空的话则无法删除元素，返回false，否则则将容器中的第一个元素删除，这里可以直接使用数组的shift方法。

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteFront = function() {
    if(this.isEmpty()) return false;
    this.list.shift();
    return true;
};

• boolean deleteLast()?：从双端队列尾部删除一个元素。如果操作成功返回 true?，否则返回 false 。
  先判断容器是否为空，为空的话则无法删除元素，返回false，否则则将容器中的第一个元素删除，这里可以直接使用数组的pop方法。

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteLast = function() {
    if(this.isEmpty()) return false;
    this.list.pop();
    return true;
};

• int getFront()?)：从双端队列头部获得一个元素。如果双端队列为空，返回 -1?。
  先判断容器是否为空，为空的话则无法取得元素，直接返回-1，否则则返回容器中的第一个元素数值。

/**
 * @return {number}
 */
MyCircularDeque.prototype.getFront = function() {
    if(this.isEmpty()) return -1;
    return this.list[0];
};

• int getRear()?：获得双端队列的最后一个元素。?如果双端队列为空，返回 -1 。
  先判断容器是否为空，为空的话则无法取得元素，直接返回-1，否则则返回容器中的最后一个元素数值。

/**
 * @return {number}
 */
MyCircularDeque.prototype.getRear = function() {
    if(this.isEmpty()) return -1;
    return this.list[this.list.length - 1];
};

• boolean isEmpty()?：若双端队列为空，则返回?true?，否则返回 false ?。
  判断当前容器中的元素数量是否为0即可。

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.isEmpty = function() {
    return this.list.length == 0;
};

• boolean isFull()?：若双端队列满了，则返回?true?，否则返回 false 。
  判断当前容器中的元素数量是否与构建时设置的最大容量数值相等。

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.isFull = function() {
    return this.list.length == this.size;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。