Categories
程式開發

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-yon/)。

創建數組:

先按照隊列的容量,創建相應長度的數組,所有元素都默認為-1。這樣獲得元素時,只要直接返回即可。使用head指針,指向隊首元素。使用tail指針,指向將要從隊尾插入元素的位置,及隊尾+1。

插入元素:

從頭部添加元素時,先將head指針向前移動一位,再將元素插入。從頭部移除元素的操作相反。從尾部添加元素時,先將元素插入到tail指針的位置,再將tail指針向後移動一位。從尾部移除元素的操作相反。

判斷隊列為空或已滿:

如果不斷添加元素,最終head指針和tail指針會相遇,此時由於tail指針的位置已有head對應的值佔據,則隊列已滿。如果不斷刪除元素,最終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;

};