Go 刷 LeetCode 系列:經(jīng)典(7) 設(shè)計雙端隊(duì)列

設(shè)計實(shí)現(xiàn)雙端隊(duì)列。

你的實(shí)現(xiàn)需要支持以下操作：

MyCircularDeque(k)：構(gòu)造函數(shù),雙端隊(duì)列的大小為k。insertFront()：將一個元素添加到雙端隊(duì)列頭部。如果操作成功返回 true。insertLast()：將一個元素添加到雙端隊(duì)列尾部。如果操作成功返回 true。deleteFront()：從雙端隊(duì)列頭部刪除一個元素。如果操作成功返回 true。deleteLast()：從雙端隊(duì)列尾部刪除一個元素。如果操作成功返回 true。getFront()：從雙端隊(duì)列頭部獲得一個元素。如果雙端隊(duì)列為空，返回 -1。getRear()：獲得雙端隊(duì)列的最后一個元素。如果雙端隊(duì)列為空，返回 -1。isEmpty()：檢查雙端隊(duì)列是否為空。isFull()：檢查雙端隊(duì)列是否滿了。示例：

MyCircularDeque circularDeque = new MycircularDeque(3); // 設(shè)置容量大小為3circularDeque.insertLast(1);              // 返回 truecircularDeque.insertLast(2);              // 返回 truecircularDeque.insertFront(3);              // 返回 truecircularDeque.insertFront(4);              // 已經(jīng)滿了，返回 falsecircularDeque.getRear();          // 返回 2circularDeque.isFull();                // 返回 truecircularDeque.deleteLast();              // 返回 truecircularDeque.insertFront(4);              // 返回 truecircularDeque.getFront();????????//?返回?4

提示：

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

操作次數(shù)的范圍為 [1, 1000]

請不要使用內(nèi)置的雙端隊(duì)列庫。

解題思路：

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

front：指向隊(duì)列頭部第 1 個有效數(shù)據(jù)的位置；

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

（說明：這個定義是依據(jù)“動態(tài)數(shù)組”的定義模仿而來。）

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

浪費(fèi)一個位置是指：循環(huán)數(shù)組中任何時刻一定至少有一個位置不存放有效元素。

判別隊(duì)列為空的條件是：front == rear;

判別隊(duì)列為滿的條件是：(rear + 1) % capacity == front;?？梢赃@樣理解，當(dāng) rear 循環(huán)到數(shù)組的前面，要從后面追上 front，還差一格的時候，判定隊(duì)列為滿。

3、因?yàn)橛醒h(huán)的出現(xiàn)，要特別注意處理數(shù)組下標(biāo)可能越界的情況。

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

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

4，如果隊(duì)列為空

插入元素的時候要注意，

（1）頭部插入，rear 后移

?（2）尾部插入，rear后移

代碼實(shí)現(xiàn)

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), //空一個位置區(qū)分滿和空        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 系列：經(jīng)典（6） 實(shí)現(xiàn)跳表
  

喜歡本文的朋友，歡迎關(guān)注“Go語言中文網(wǎng)”：

Go語言中文網(wǎng)啟用微信學(xué)習(xí)交流群，歡迎加微信：274768166，投稿亦歡迎