641. 设计循环双端队列

🟠   🔖  设计 队列 数组 链表  🔗 力扣 LeetCode

题目

Design your implementation of the circular double-ended queue (deque).

Implement the MyCircularDeque class:

• MyCircularDeque(int k) Initializes the deque with a maximum size of k.
• boolean insertFront() Adds an item at the front of Deque. Returns true if the operation is successful, or false otherwise.
• boolean insertLast() Adds an item at the rear of Deque. Returns true if the operation is successful, or false otherwise.
• boolean deleteFront() Deletes an item from the front of Deque. Returns true if the operation is successful, or false otherwise.
• boolean deleteLast() Deletes an item from the rear of Deque. Returns true if the operation is successful, or false otherwise.
• int getFront() Returns the front item from the Deque. Returns -1 if the deque is empty.
• int getRear() Returns the last item from Deque. Returns -1 if the deque is empty.
• boolean isEmpty() Returns true if the deque is empty, or false otherwise.
• boolean isFull() Returns true if the deque is full, or false otherwise.

Example 1:

Input

["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]

[[3], [1], [2], [3], [4], [], [], [], [4], []]

Output

[null, true, true, true, false, 2, true, true, true, 4]

Explanation

MyCircularDeque myCircularDeque = new MyCircularDeque(3);

myCircularDeque.insertLast(1); // return True

myCircularDeque.insertLast(2); // return True

myCircularDeque.insertFront(3); // return True

myCircularDeque.insertFront(4); // return False, the queue is full.

myCircularDeque.getRear(); // return 2

myCircularDeque.isFull(); // return True

myCircularDeque.deleteLast(); // return True

myCircularDeque.insertFront(4); // return True

myCircularDeque.getFront(); // return 4

Constraints:

• 1 <= k <= 1000
• 0 <= value <= 1000
• At most 2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.

题目大意

设计实现双端队列。

实现 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 。

解题思路

可以使用数组来实现双端队列，其中:

• insertFront 对应数组的 unshift 方法；
• insertLast 对应数组的 push 方法；
• deleteFront 对应数组的 shift 方法；
• deleteLast 对应数组的 pop 方法；
• getFront 和 getRear 对应查看数组第一个和最后一个元素；
• isEmpty 和 isFull 对应查看数组长度为空或者为 K；

代码

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

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

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

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteFront = function () {
	if (this.arr.length > 0) {
		this.arr.shift();
		return true;
	}
	return false;
};

/**
 * @return {boolean}
 */
MyCircularDeque.prototype.deleteLast = function () {
	if (this.arr.length > 0) {
		this.arr.pop();
		return true;
	}
	return false;
};

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

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

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

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

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * var obj = new MyCircularDeque(k)
 * var param_1 = obj.insertFront(value)
 * var param_2 = obj.insertLast(value)
 * var param_3 = obj.deleteFront()
 * var param_4 = obj.deleteLast()
 * var param_5 = obj.getFront()
 * var param_6 = obj.getRear()
 * var param_7 = obj.isEmpty()
 * var param_8 = obj.isFull()
 */

相关题目

题号	标题	题解	标签	难度
622	设计循环队列	[✓]	设计 队列 数组 1+
1670	设计前中后队列		设计 队列 数组 2+