數(shù)據(jù)結(jié)構(gòu)實現(xiàn) 1.3：數(shù)組隊列（C++版）

• 1. 概念及基本框架

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

• 2.1 入隊操作

• 2.2 出隊操作

• 2.3 查找操作

• 2.4 其他操作

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

• 3.1 入隊操作

• 3.2 出隊操作

• 3.3 查找操作

• 4. 完整代碼

1. 概念及基本框架

隊列?可以看做一種特殊的?數(shù)組?，所以我使用第一節(jié)實現(xiàn)的?動態(tài)數(shù)組?來實現(xiàn)隊列這種數(shù)據(jù)結(jié)構(gòu)。當(dāng)然，隊列也可以通過其他方式來實現(xiàn)。因為該隊列是通過動態(tài)數(shù)組實現(xiàn)的，所以稱之為?數(shù)組隊列?。

隊列的結(jié)構(gòu)如上圖所示，可知隊列的基本特性如下：
1.隊列?有?隊頭?和?隊尾?兩端。
2.入隊?操作只能從?隊尾?進行，出隊?操作只能從?隊頭?進行。
3.先?入隊?的先?出隊?，即?先進先出（First In First Out），FIFO?。
還有一個隱含特性，隊列可以自行?擴容（縮容），而不需要用戶關(guān)心，很顯然，動態(tài)數(shù)組已經(jīng)滿足了這個要求。
由此可見，隊列的操作并不多，我使用了一個由?純虛函數(shù)?構(gòu)成的?抽象類?作為一個接口來定義這些操作。具體代碼如下：

下面只需要通過繼承?抽象類，并且重寫?純虛函數(shù)?，就可以完成?數(shù)組隊列?的實現(xiàn)。數(shù)組隊列類的框架如下：

這個類內(nèi)部定義一個動態(tài)數(shù)組類對象，為了保護數(shù)據(jù)，把它放在?private?部分，構(gòu)造函數(shù)?ArrayQueue?底層調(diào)用的就是?Array?的構(gòu)造函數(shù)。用戶在構(gòu)造函數(shù)中也可以指定隊列的大小。（默認是10）為了兼容更多類型，這里使用了泛型的概念。

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

2.1 入隊操作

入隊操作使用了動態(tài)數(shù)組的增加第一個元素的操作來實現(xiàn)。這里動態(tài)數(shù)組內(nèi)部已經(jīng)提供了擴容操作。

2.2 出隊操作

出隊操作使用了動態(tài)數(shù)組的刪除第一個元素的操作來實現(xiàn)。這里動態(tài)數(shù)組內(nèi)部已經(jīng)提供了縮容操作。

2.3 查找操作

因為隊列只能獲得隊首元素，所以這里的查找操作也非常簡單。

2.4 其他操作

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

3.1 入隊操作

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

3.2 出隊操作

3.3 查找操作

總體情況：

由此可以看出，隊列操作的增、查都是?O(1)?級別的時間復(fù)雜度，而刪是?O(n)?級別的時間復(fù)雜度，因為每次出隊的都是隊首元素，后面的元素需要一個個向前移動。
注：隊列并不提供改的操作。

4. 完整代碼

動態(tài)數(shù)組類?代碼：

抽象類?接口代碼：

數(shù)組隊列?代碼：