設計實現雙端隊列。

你的實現需要支持以下操作：

MyCircularDeque(k)：構造函數,雙端隊列的大小為k。insertFront()：將一個元素添加到雙端隊列頭部。如果操作成功返回 true。insertLast()：將一個元素添加到雙端隊列尾部。如果操作成功返回 true。deleteFront()：從雙端隊列頭部刪除一個元素。如果操作成功返回 true。deleteLast()：從雙端隊列尾部刪除一個元素。如果操作成功返回 true。getFront()：從雙端隊列頭部獲得一個元素。如果雙端隊列為空，返回 -1。getRear()：獲得雙端隊列的最后一個元素。如果雙端隊列為空，返回 -1。isEmpty()：檢查雙端隊列是否為空。isFull()：檢查雙端隊列是否滿了。示例：MyCircularDeque circularDeque = new MycircularDeque(3); // 設置容量大小為3circularDeque.insertLast(1); // 返回 truecircularDeque.insertLast(2); // 返回 truecircularDeque.insertFront(3); // 返回 truecircularDeque.insertFront(4); // 已經滿了，返回 falsecircularDeque.getRear(); // 返回 2circularDeque.isFull(); // 返回 truecircularDeque.deleteLast(); // 返回 truecircularDeque.insertFront(4); // 返回 truecircularDeque.getFront();????????//?返回?4

提示：

所有值的范圍為 [1, 1000]

操作次數的范圍為 [1, 1000]

請不要使用內置的雙端隊列庫。

解題思路：

1、定義循環變量 front 和 rear 。一直保持這個定義，到底是先賦值還是先移動指針就很容易想清楚了。

front：指向隊列頭部第 1 個有效數據的位置；

rear：指向隊列尾部(即最后 1 個有效數據)的下一個位置，即下一個從隊尾入隊元素的位置。

(說明：這個定義是依據“動態數組”的定義模仿而來。)

2、為了避免“隊列為空”和“隊列為滿”的判別條件沖突，我們有意浪費了一個位置。

浪費一個位置是指：循環數組中任何時刻一定至少有一個位置不存放有效元素。

判別隊列為空的條件是：front == rear;

判別隊列為滿的條件是：(rear + 1) % capacity == front;。可以這樣理解，當 rear 循環到數組的前面，要從后面追上 front，還差一格的時候，判定隊列為滿。

3、因為有循環的出現，要特別注意處理數組下標可能越界的情況。

(1)指針后移的時候，索引 + 1，要取模；

(2)指針前移的時候，為了循環到數組的末尾，需要先加上數組的長度，然后再對數組長度取模。

4，如果隊列為空

插入元素的時候要注意，

(1)頭部插入，rear 后移

?(2)尾部插入，rear后移

代碼實現

type MyCircularDeque struct { length int data []int head int rear int}/** Initialize your data structure here. Set the size of the deque to be k. */func Constructor(k int) MyCircularDeque { return MyCircularDeque{ length:k+1, data:make([]int,k+1), //空一個位置區分滿和空 head:0, rear:0, }}/** Adds an item at the front of Deque. Return true if the operation is successful. */func (this *MyCircularDeque) InsertFront(value int) bool { if this.IsFull(){ return false } if this.IsEmpty(){ if this.rear==this.length-1{ this.rear=0 }else{ this.rear++ } this.data[this.head]=value return true } if this.head==0{ this.head=this.length-1 }else{ this.head-- } this.data[this.head]=value return true}/** Adds an item at the rear of Deque. Return true if the operation is successful. */func (this *MyCircularDeque) InsertLast(value int) bool { if this.IsFull(){ return false } if this.IsEmpty(){ this.data[this.rear]=value if this.rear==this.length-1{ this.rear=0 }else{ this.rear++ } return true } this.data[this.rear]=value if this.rear==this.length-1{ this.rear=0 }else{ this.rear++ } return true}/** Deletes an item from the front of Deque. Return true if the operation is successful. */func (this *MyCircularDeque) DeleteFront() bool { if this.IsEmpty(){ return false } if this.head==this.length-1{ this.head=0 }else{ this.head++ } return true}/** Deletes an item from the rear of Deque. Return true if the operation is successful. */func (this *MyCircularDeque) DeleteLast() bool { if this.IsEmpty(){ return false } if this.rear==0{ this.rear=this.length-1 }else{ this.rear-- } return true}/** Get the front item from the deque. */func (this *MyCircularDeque) GetFront() int { if this.IsEmpty(){ return -1 } return this.data[this.head] }/** Get the last item from the deque. */func (this *MyCircularDeque) GetRear() int { if this.IsEmpty(){ return -1 } if this.rear==0{ return this.data[this.length-1] } return this.data[this.rear-1]}/** Checks whether the circular deque is empty or not. */func (this *MyCircularDeque) IsEmpty() bool { return this.head==this.rear}/** Checks whether the circular deque is full or not. */func (this *MyCircularDeque) IsFull() bool { return (this.rear+1)%this.length==this.head}/** * Your MyCircularDeque object will be instantiated and called as such: * obj := Constructor(k); * param_1 := obj.InsertFront(value); * param_2 := obj.InsertLast(value); * param_3 := obj.DeleteFront(); * param_4 := obj.DeleteLast(); * param_5 := obj.GetFront(); * param_6 := obj.GetRear(); * param_7 := obj.IsEmpty(); * param_8 := obj.IsFull(); */

推薦閱讀

• Go 刷 LeetCode 系列：經典(6) 實現跳表

---

喜歡本文的朋友，歡迎關注“Go語言中文網”：

Go語言中文網啟用微信學習交流群，歡迎加微信：274768166，投稿亦歡迎

總結

以上是生活随笔為你收集整理的sv队列和动态数组的区别_Go 刷 LeetCode 系列：经典（7） 设计双端队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。