數(shù)據(jù)結(jié)構(gòu)實現(xiàn) 2.3：鏈表隊列（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. 概念及基本框架

在前面第三節(jié)中，我們通過?動態(tài)數(shù)組?實現(xiàn)了?隊列?這種數(shù)據(jù)結(jié)構(gòu)。當(dāng)然，隊列也可以通過?鏈表?來實現(xiàn)所謂的?鏈表隊列?。

鏈表隊列的結(jié)構(gòu)如上圖所示，鏈表隊列有著隊列的基本特性：
1.隊列?有?隊頭?和?隊尾?兩端。
2.入隊?操作只能從?隊尾?進(jìn)行，出隊?操作只能從?隊頭?進(jìn)行。
3.先?入隊?的先?出隊?，即?先進(jìn)先出（First In First Out），FIFO?。
因為鏈表對鏈表末端操作時間復(fù)雜度較大，所以添加了一個?tail?指針，使得原來?O(n)?的時間復(fù)雜度變成了?O(1)?級別的。由于?tail?指針的加入，而且我們的操作也只針對?head?和?tail?，所以可以去掉虛擬頭結(jié)點，因此我們需要從底層來重新構(gòu)建這個類。
與數(shù)組隊列類似，可以利用一個由?純虛函數(shù)?構(gòu)成的?抽象類?作為一個接口來定義這些操作。具體代碼如下：

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

其中的?Node?類是第五節(jié)鏈表中定義的一個類，這里不再重復(fù)定義，直接使用，Node?類的定義如下：

LinkedListQueue?類內(nèi)部定義頭指針、尾指針以及鏈表長度，為了保護數(shù)據(jù)，把變量都放在?private?部分，為了兼容更多類型，這里使用了泛型的概念。

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

2.1 入隊操作

由于使用了尾指針，入隊操作十分方便。但是要注意，當(dāng)鏈表為空時的特殊情況。

2.2 出隊操作

2.3 查找操作

隊列只能獲得隊首元素。

2.4 其他操作

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

3.1 入隊操作

3.2 出隊操作

3.3 查找操作

總體情況：

由此可以看出，鏈表隊列操作的增、刪、查都是?O(1)?級別的時間復(fù)雜度。

注：隊列并不提供改的操作。

4. 完整代碼

Node類?代碼：

抽象類?接口代碼：

鏈表隊列?代碼：