實現一個雙端隊列的步驟簡析

01 故事起源

隊列是一種先進先出的數據結構。
?

一般通過數組實現。

?

還需要定義2個指針，頭指針和尾指針。

?

02 插入和刪除

2.1 插入

從隊尾tail處插入，再將tail指針后移。

2.2 刪除

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

?

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

?

03 循環(huán)隊列

循環(huán)其實就是讓head,tail兩個指針在數組內循環(huán)移動，當移動到隊尾時就跳到隊首。

?

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

?

當head==tail時，即為隊空。

?

當head==(tail+1)%n時，即為隊滿。如果隊列長度為n，則只能裝n-1個元素，最后一個元素要空著。因為如果放入元素，tail會和head重合，就無法判斷是隊空還是隊滿。

? ?

04 雙端隊列

普通隊列只能隊首出，隊尾進，但有時我們需要隊首和隊尾都能進出，即雙端隊列。

4.1 插入

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

4.2 刪除

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

?

05 代碼實現

實現一個模板，以后可重復利用。

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

構造函數