数据结构实现 2.2：链表栈（C++版）

1. 概念及基本框架

(相关资料图)

2. 基本操作程序实现

2.1 入栈操作

2.2 出栈操作

2.3 查找操作

2.4 其他操作

3. 算法复杂度分析

3.1 入栈操作

3.2 出栈操作

3.3 查找操作

4. 完整代码

1. 概念及基本框架

通过第五节，我们知道链表虽然整体的操作时间复杂度是 O(n)级别的，但是如果只对头结点进行操作，那么时间复杂度是 O(1)级别的，这很类似于栈（单口容器）的操作。在第二节中，我们利用 数组实现了 栈这种数据结构。当然，栈也可以通过 链表来实现。下面通过链表来实现 链表栈。

链表栈的结构如上图所示，链表栈有着栈的基本特性：1.栈有 栈顶和 栈底两端。2.入栈和 出栈操作只能从 栈顶进行。3.后 入栈的先 出栈，即 后进先出（Last In First Out），LIFO。与数组栈类似，依旧使用由 纯虚函数构成的 抽象类作为一个接口来定义栈的基本操作。具体代码如下：

下面只需要通过继承 抽象类，并且重写 纯虚函数，就可以完成 链表栈的实现。链表栈类的框架如下：

这个类内部定义一个链表类对象，为了保护数据，把它放在 private部分。因为 LinkedListStack类包含了 LinkedList类，所以构造函数 LinkedListStack会自动调用 LinkedList的构造函数。为了兼容更多类型，这里使用了泛型的概念。

2. 基本操作程序实现

2.1 入栈操作

入栈操作使用了链表的增加第一个元素的操作来实现。

2.2 出栈操作

出栈操作使用了链表的删除第一个元素的操作来实现。

2.3 查找操作

因为栈只能获得栈顶元素，所以这里的查找操作也非常简单。

2.4 其他操作

3. 算法复杂度分析

3.1 入栈操作

3.2 出栈操作

3.3 查找操作

总体情况：

因为都是针对第一个元素的操作，链表栈操作都是 O(1)级别的时间复杂度，而且相较数组栈而言，省去了扩容（缩容）操作。注：这里并没有改的操作，如果更改，需要先出栈，再入栈。

4. 完整代码

链表类代码：

抽象类接口代码：

链表栈代码：

标签：