Summary

• 什么是環(huán)形隊(duì)列
• 實(shí)現(xiàn)環(huán)形隊(duì)列圖示過程
• golang版本代碼實(shí)現(xiàn)過程
• 參考全部代碼

什么是環(huán)形隊(duì)列

在一個(gè)指定大小的數(shù)組里循環(huán)寫入數(shù)據(jù),借用二個(gè)指針分別實(shí)現(xiàn)入隊(duì)標(biāo)記與出隊(duì)標(biāo)記.也體現(xiàn)了指針的大好用處,請深入體會.大有裨益.

如圖所示,一個(gè)環(huán)形隊(duì)列.含有二個(gè)指針: 隊(duì)列頭指針,隊(duì)列尾指針.

實(shí)現(xiàn)環(huán)形隊(duì)列圖示過程

初始化一個(gè)數(shù)組大小為6的環(huán)形隊(duì)列, 頭指針front=0, 尾指針rear=0, 剛好front=rear =0的狀態(tài),表示環(huán)形隊(duì)列為空.

2.向環(huán)形隊(duì)列里插入1個(gè)元素,則rear指針移動一格,front=0,rear=1

3.繼續(xù)添加a2,a3,a4,a5元素,rear指針指到末尾處,front=0, reat=5

4.如果再繼續(xù)添加a6元素,則rear=6,大于數(shù)組大小,發(fā)生數(shù)組溢出.

5.如上圖所示添加a6時(shí),rear指針發(fā)生溢出.我們使用一個(gè)小技巧,當(dāng)rear=6時(shí)與數(shù)組大小6進(jìn)行取模, (rear+1) % maxLen,讓rear指針回到開始處rear=0,問題來了,我們無法判斷數(shù)組是否滿?因?yàn)槌跏蓟瘯r(shí)front=rear=0, 現(xiàn)在數(shù)組滿也是front=rear=0

6.解決以上問題有三種辦法,我們采用第3種方法實(shí)現(xiàn).

使用第3種方法: 即當(dāng)(rear+1) % maxLen == front時(shí),判斷環(huán)形數(shù)組滿,則無法添加元素

golang版代碼實(shí)現(xiàn)過程

a. 定義環(huán)形數(shù)據(jù)結(jié)構(gòu)

type CycleQueue struct {
 data []interface{} //存儲空間
 front int      //前指針,前指針負(fù)責(zé)彈出數(shù)據(jù)移動
 rear int      //尾指針,后指針負(fù)責(zé)添加數(shù)據(jù)移動
 cap  int      //設(shè)置切片最大容量 
}

b.初始化環(huán)形隊(duì)列

func NewCycleQueue(cap int) *CycleQueue {
 return CycleQueue{
  data: make([]interface{}, cap),
  cap:  cap,
  front: 0,
  rear: 0,
 }
}

c. 入隊(duì)操作

//入隊(duì)操作
//判斷隊(duì)列是否隊(duì)滿,隊(duì)滿則不允許添加數(shù)據(jù)
func (q *CycleQueue) Push(data interface{}) bool {
 //check queue is full
 if (q.rear+1)%q.cap == q.front { //隊(duì)列已滿時(shí)，不執(zhí)行入隊(duì)操作
  return false
 }
 q.data[q.rear] = data     //將元素放入隊(duì)列尾部
 q.rear = (q.rear + 1) % q.cap //尾部元素指向下一個(gè)空間位置,取模運(yùn)算保證了索引不越界（余數(shù)一定小于除數(shù)）
 return true
}

d.出隊(duì)操作

//出隊(duì)操作
//需要考慮: 隊(duì)隊(duì)為空沒有數(shù)據(jù)返回了
func (q *CycleQueue) Pop() interface{} {
 if q.rear == q.front {
  return nil
 }
 data := q.data[q.front]
 q.data[q.front] = nil
 q.front = (q.front + 1) % q.cap
 return data
}

e:求當(dāng)前的環(huán)形隊(duì)列長度

//因?yàn)槭茄h(huán)隊(duì)列, 后指針減去前指針 加上最大值, 然后與最大值 取余
func (q *CycleQueue) QueueLength() int {
 return (q.rear - q.front + q.cap) % q.cap
}

參考全部代碼

github

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。