[路飛]_leetcode 641. 設計雙向迴圈佇列 JavaScript版

語言: CN / TW / HK

「這是我參與11月更文挑戰的第 10 天,活動詳情檢視:2021最後一次更文挑戰

題目

題目來源:641. 設計雙向迴圈佇列

設計實現雙端佇列。

你的實現需要支援以下操作:\ vMyCircularDeque(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]\ 請不要使用內建的雙端佇列庫。

  • 首先建立容量為k的陣列,用來儲存資料

  • 定義變數:

  • capacity 表示佇列最大容量
  • front 表示隊首的索引
  • rear 表示隊尾的索引 它指向下一個從隊尾入隊元素的位置
  • count 表示當前佇列長度

  • capacity 初始值為k

  • frony 初始值為0
  • rear 初始值為0
  • count 初始值為0,count == 0 當前佇列為空

1636629806(1).png

  • 從隊尾新增一個元素時,向queue[rear]位置插入元素

  • 然後隊尾索引向後移動rear=(rear+1)%capacity,並且count++

1636629980(1).png

  • 從隊首刪除一個元素時,front向後移動即可,front=(front+1)%capacity,count--

1636630263(1).png

  • 從隊尾新增一個元素時,rear = (rear+1) % capacity,並且count++

1636630238(1).png

  • 從對首新增一個元素,front先向前移動一位,front=(front-1+capacity)%capacity,並且count++

1636630581(1).png

  • 此時繼續新增元素,當capacitycount相等時,說明佇列已滿.

1636630664(1).png

程式碼實現

```js /* * @param {number} k / var MyCircularDeque = function(k) { this.queue = new Array(k+1) // 用來模擬佇列的陣列 this.front = 0 // 頭指標 this.rear = 0 // 尾指標 this.max = k // 記錄當前最大容器 };

/* * @param {number} value * @return {boolean} / MyCircularDeque.prototype.insertFront = function(value) { if(this.isFull()) return false; this.front = (this.front + this.max) % (this.max + 1) this.queue[this.front] = value return true };

/* * @param {number} value * @return {boolean} / MyCircularDeque.prototype.insertLast = function(value) { if(this.isFull()) return false; this.queue[this.rear] = value; this.rear = (this.rear + 1) % (this.max + 1) return true };

/* * @return {boolean} / MyCircularDeque.prototype.deleteFront = function() { if(this.isEmpty()) return false; this.front = (this.front + 1) % (this.max + 1) return true };

/* * @return {boolean} / MyCircularDeque.prototype.deleteLast = function() { if(this.isEmpty()) return false; // 刪除佇列元素的最後一個元素,那麼尾指標rear,往前移動一位 this.rear = (this.rear + this.max) % (this.max + 1) return true };

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

/* * @return {number} / MyCircularDeque.prototype.getRear = function() { if(this.isEmpty()) return -1; return this.queue[(this.rear + this.max) % (this.max + 1)] };

/* * @return {boolean} / MyCircularDeque.prototype.isEmpty = function() { return ((this.rear - this.front + this.max + 1) % (this.max+1)) == 0 };

/* * @return {boolean} / MyCircularDeque.prototype.isFull = function() { return ((this.rear - this.front + this.max + 1) % (this.max+1)) == this.max }; ```