01 故事起源

隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。
?

一般通過數(shù)組實(shí)現(xiàn)。

?

還需要定義2個(gè)指針，頭指針和尾指針。

?

02 插入和刪除

2.1 插入

從隊(duì)尾tail處插入，再將tail指針后移。

2.2 刪除

從隊(duì)首head處取出元素，再將head指針后移。

?

但數(shù)組是定長的，如果多次插入刪除，tail指針就會(huì)超出數(shù)組范圍，而前面其實(shí)還是有空間的，所以常用的還是循環(huán)隊(duì)列。

?

03 循環(huán)隊(duì)列

循環(huán)其實(shí)就是讓head,tail兩個(gè)指針在數(shù)組內(nèi)循環(huán)移動(dòng)，當(dāng)移動(dòng)到隊(duì)尾時(shí)就跳到隊(duì)首。

?

通過取模就可以實(shí)現(xiàn)循環(huán)。

?

當(dāng)head==tail時(shí)，即為隊(duì)空。

?

當(dāng)head==(tail+1)%n時(shí)，即為隊(duì)滿。如果隊(duì)列長度為n，則只能裝n-1個(gè)元素，最后一個(gè)元素要空著。因?yàn)槿绻湃朐?，tail會(huì)和head重合，就無法判斷是隊(duì)空還是隊(duì)滿。

? ?

04 雙端隊(duì)列

普通隊(duì)列只能隊(duì)首出，隊(duì)尾進(jìn)，但有時(shí)我們需要隊(duì)首和隊(duì)尾都能進(jìn)出，即雙端隊(duì)列。

4.1 插入

隊(duì)首插入，則head指針前移；隊(duì)尾插入，則tail指針后移。

4.2 刪除

隊(duì)首刪除，則head指針后移；隊(duì)尾刪除，則tail指針前移。

?

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

實(shí)現(xiàn)一個(gè)模板，以后可重復(fù)利用。

先定義必要的方法和變量。

構(gòu)造函數(shù)