數(shù)據(jù)結(jié)構(gòu)實現(xiàn) 2.2：鏈表棧（C++版）

1. 概念及基本框架

(相關(guān)資料圖)

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

2.1 入棧操作

2.2 出棧操作

2.3 查找操作

2.4 其他操作

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

3.1 入棧操作

3.2 出棧操作

3.3 查找操作

4. 完整代碼

1. 概念及基本框架

通過第五節(jié)，我們知道鏈表雖然整體的操作時間復(fù)雜度是?O(n)級別的，但是如果只對頭結(jié)點進行操作，那么時間復(fù)雜度是?O(1)級別的，這很類似于棧（單口容器）的操作。在第二節(jié)中，我們利用?數(shù)組實現(xiàn)了?棧這種數(shù)據(jù)結(jié)構(gòu)。當然，棧也可以通過?鏈表來實現(xiàn)。下面通過鏈表來實現(xiàn)?鏈表棧。

鏈表棧的結(jié)構(gòu)如上圖所示，鏈表棧有著棧的基本特性：1.棧有?棧頂和?棧底兩端。2.入棧和?出棧操作只能從?棧頂進行。3.后?入棧的先?出棧，即?后進先出（Last In First Out），LIFO。與數(shù)組棧類似，依舊使用由?純虛函數(shù)構(gòu)成的?抽象類作為一個接口來定義棧的基本操作。具體代碼如下：

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

這個類內(nèi)部定義一個鏈表類對象，為了保護數(shù)據(jù)，把它放在?private部分。因為?LinkedListStack類包含了?LinkedList類，所以構(gòu)造函數(shù)?LinkedListStack會自動調(diào)用?LinkedList的構(gòu)造函數(shù)。為了兼容更多類型，這里使用了泛型的概念。

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

2.1 入棧操作

入棧操作使用了鏈表的增加第一個元素的操作來實現(xiàn)。

2.2 出棧操作

出棧操作使用了鏈表的刪除第一個元素的操作來實現(xiàn)。

2.3 查找操作

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

2.4 其他操作

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

3.1 入棧操作

3.2 出棧操作

3.3 查找操作

總體情況：

因為都是針對第一個元素的操作，鏈表棧操作都是?O(1)級別的時間復(fù)雜度，而且相較數(shù)組棧而言，省去了擴容（縮容）操作。注：這里并沒有改的操作，如果更改，需要先出棧，再入棧。

4. 完整代碼

鏈表類代碼：

抽象類接口代碼：

鏈表棧代碼：