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

• 1. 概念及基本框架

• 2. 基本操作程序實現(xiàn)

• 2.1 入棧操作

• 2.2 出棧操作

• 2.3 查找操作

• 2.4 其他操作

• 3. 算法復雜度分析

• 3.1 入棧操作

• 3.2 出棧操作

• 3.3 查找操作

• 4. 完整代碼

1. 概念及基本框架

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

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

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

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

2. 基本操作程序實現(xiàn)

2.1 入棧操作

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

2.2 出棧操作

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

2.3 查找操作

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

2.4 其他操作

3. 算法復雜度分析

3.1 入棧操作

3.2 出棧操作

3.3 查找操作

總體情況：

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

4. 完整代碼

鏈表類?代碼：

抽象類?接口代碼：

鏈表棧?代碼：