數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn) 1.4：循環(huán)隊(duì)列（C++版）

• 1. 概念及基本框架

• 2. 基本操作程序?qū)崿F(xiàn)

• 2.1 入隊(duì)操作

• 2.2 出隊(duì)操作

• 2.3 查找操作

• 2.4 其他操作

• 3. 算法復(fù)雜度分析

• 3.1 入隊(duì)操作

• 3.2 出隊(duì)操作

• 3.3 查找操作

• 4. 完整代碼

1. 概念及基本框架

通過第三節(jié)我們知道，數(shù)組隊(duì)列?在出隊(duì)操作中需要花費(fèi)?O(n)?的時間復(fù)雜度，原因在于出隊(duì)時需要移動大量元素。如果我們可以循環(huán)利用空間，那么問題就迎刃而解。所以，循環(huán)隊(duì)列?應(yīng)運(yùn)而生。循環(huán)隊(duì)列結(jié)構(gòu)如下：
（這里為了直觀，將隊(duì)列繪制成環(huán)形，實(shí)際內(nèi)存依舊是連續(xù)的內(nèi)存塊。）

首先循環(huán)隊(duì)列作為隊(duì)列的一種，基本特性和數(shù)組隊(duì)列相同：
1.隊(duì)列?有?隊(duì)頭?和?隊(duì)尾?兩端。
2.入隊(duì)?操作只能從?隊(duì)尾?進(jìn)行，出隊(duì)?操作只能從?隊(duì)頭?進(jìn)行。
3.先?入隊(duì)?的先?出隊(duì)?，即?先進(jìn)先出（First In First Out），FIFO?。
還有一個隱含特性，隊(duì)列可以自行?擴(kuò)容（縮容），而不需要用戶關(guān)心。
由上圖結(jié)構(gòu)可知，隊(duì)空和隊(duì)滿時，隊(duì)頭和隊(duì)尾都指向同一塊內(nèi)存。因?yàn)檠h(huán)隊(duì)列和動態(tài)數(shù)組有一定差異，所以對循環(huán)隊(duì)列從底層重新進(jìn)行了實(shí)現(xiàn)。首先，依舊使用一個由?純虛函數(shù)?構(gòu)成的?抽象類?作為一個接口來定義這些操作。具體代碼如下：

下面從底層重新構(gòu)建一個循環(huán)隊(duì)列類。

這個類內(nèi)部定義一個數(shù)組，為了兼容更多類型，這里使用了泛型的概念。然后定義了隊(duì)列的容量、大小以及隊(duì)頭和隊(duì)尾。同理，構(gòu)造數(shù)組時，可以初始化隊(duì)列的隊(duì)列容量，（默認(rèn)是10）隊(duì)頭和隊(duì)尾都是0。
與動態(tài)數(shù)組類似，為了實(shí)現(xiàn)自行?擴(kuò)容（縮容），類內(nèi)部創(chuàng)建了一個?resize?函數(shù)來實(shí)現(xiàn)。

原理上與動態(tài)數(shù)組類似，這里的?取余?操作保證了循環(huán)。下面對各種基本操作進(jìn)行了重寫實(shí)現(xiàn)。

2. 基本操作程序?qū)崿F(xiàn)

2.1 入隊(duì)操作

入隊(duì)操作時可能會調(diào)用?擴(kuò)容函數(shù)?。

2.2 出隊(duì)操作

出隊(duì)操作時可能會調(diào)用?縮容函數(shù)?。

2.3 查找操作

同樣的，隊(duì)列只能獲得隊(duì)首元素，所以這里的查找操作也非常簡單。

2.4 其他操作

為了保證正確輸出，print?函數(shù)中也采用了?取余?操作。

3. 算法復(fù)雜度分析

3.1 入隊(duì)操作

最壞復(fù)雜度?O(1+n)?中第一個?1?是指元素移動操作，第二個?n?是指?resize?函數(shù)，以下同理。
入隊(duì)可能會引發(fā)擴(kuò)容操作，平均而言，每增加?n?個元素，會擴(kuò)展一次，會發(fā)生?n?個元素的移動，所以平均下來是?O(1)?。

3.2 出隊(duì)操作

3.3 查找操作

總體情況：

通過第三節(jié)我們知道，數(shù)組隊(duì)列操作的增、查都是?O(1)?級別的時間復(fù)雜度，而刪是?O(n)?級別的時間復(fù)雜度，因?yàn)槊看纬鲫?duì)的都是隊(duì)首元素，后面的元素需要一個個向前移動。而對于循環(huán)隊(duì)列，不需要移動元素，所以增、刪、查都是?O(1)?級別的時間復(fù)雜度，實(shí)現(xiàn)了對數(shù)組隊(duì)列的優(yōu)化。
注：隊(duì)列并不提供改的操作。

4. 完整代碼

抽象類?接口代碼：

循環(huán)隊(duì)列?代碼：