顺序栈与链栈

概念

栈和队列不是新的数据结构，它们也是线性表，只不过它们是操作受限的线性表。为什么这样说？因为线性表无论是顺序表还是链表都是支持在任何位置进行插入的，但是栈和队列的话，它们不允许在任何位置上进行插入和删除，而是有一定的限制：

1. 对于栈来说，只允许在栈的尾部，当然我是基于顺序表的特征来说的，往往在讨论栈的时候，会将其倒置，头部向下，尾部向上，这样的话，尾部的插入与删除，就变成了在栈顶进行插入和删除，这也造就了栈的一个很大的特点，那就是元素是先进后出(FILO)，后进先出(LIFO)。类比生活中的堆盘子，最下面的盘子往往是第一个放置的。关于栈的一些名词如下：

   • 栈顶、栈底

   • 出栈：栈顶删除元素

   • 入栈：栈顶插入元素

   • 栈空、栈满：需要根据依赖的底层物理结构来去判断

2. 对于队列来说，允许在队列的头部进行删除，允许在队列的尾部进行插入，这也造就了队列的一个很大的特点，那就是先进后出(FIFO)，后进后出(LILO)。类比生活中的排队买饭，队头往往是第一个买都的。

   • 队头、队尾

   • 出队：在队头删除元素

   • 入队：在队尾插入元素

   • 队空、队满

由于栈和队列在生活中的例子非常多，它的应用也是非常广泛的，毕竟数据结构就是用来解决问题的。

顺序栈

顺序栈：基于顺序表实现的栈，栈内每个元素的地址是连续的。

在自己实现顺序栈的时候，遇到一个比较纠结的问题，那就是指向栈顶指针的初始化问题，看一下图示吧：

假设，左右两边的栈容量都是只能存放5个元素：

1. 左边的图示中：top一开始的初始化为-1，那么在栈内至少有一个有效元素的时候，这个top实际每次指向的就是当前栈最后一个有效元素，它的语义在此时就是数组中栈顶元素的物理索引。

   • 当top == -1的时候，栈空

   • 当top + 1 == 5的时候，栈满

   • 入栈时，除了判断栈是否满之外，需要先将top + 1，在写入数据，也就是先移动top指针，再写入数据

   • 出栈时：出了判断栈是否空之外，直接将top - 1即可，因为top的含义就是指向栈内最后一个有效元素嘛。

   • 当栈至少有一个有效元素的时候，可通过top直接获取栈顶，因为此时top保存的就是栈顶元素所在的下标

2. 右边的图示中：top一开始的初始化为0，它指向永远是下一个元素要插入的位置，也就是栈内至少有一个有效元素的时候，这个top实际每次指向的就是当前栈内最后一个有效元素的后一个位置。它的语义就是数组中栈顶后一个待插入元素的数组索引

   • 当top == 0的时候，栈空

   • 当top == 5的时候，栈满

   • 入栈时：除了判断栈是否满之外，直接通过top插入元素，再移动top指针。与top == -1是相反的，它是先写入数据，再移动指针。

   • 出栈时：除了判断栈是否空之外，直接将top - 1即可，top的含义就是指向下一个要插入的位置，将top - 1，就是将来入栈的时候将原来的栈顶元素覆盖，实现出栈的效果

   • 当栈至少有一个有效元素的时候，获取栈顶元素，此时要注意：不是要将top本身-1获取栈顶元素的，那样的话，你若是调用一次获取栈顶元素的接口，top本身的值减去1的话，那么就相当于一次栈顶元素出栈，每次获取的栈顶元素都不一样的，我们做的是获取栈顶元素，不是出栈。实际上是使用top - 1的值作为下标来获取栈顶元素

通过以上的说明，你会发现，两种初始化top的方式，都有方便操作的地方，只要明白原理即可。但本质还有区别的，从底层架构的视角去看待这个问题。

满栈(full stack)与空栈(empty stack)

通过查阅资料，在CPU硬件层面，这两种初始化的方式还有特别的定义：

满栈(full stack)

它对应的就是top == -1。栈指针(stack pointer)永远指向栈顶包含有效数据的那个内存单元。常见的X86架构下使用的就是满栈设计（具体为满递减栈 FD，Full Descending）。在 x86 中执行 push rax，CPU 是先移动rsp，再把数据写进去。

空栈(empty stack)

它对应的就是top == 0。栈指针(stack pointer)指向的是栈顶的下一个空闲内存单元，在压栈时，是先写数据，再移动指针。

我比较倾向于空栈的初始化方式，因为它完美符合左闭右开区间思想[0,top)，与C++迭代器的思想很像，0是begin，end是top。左闭右开的区间思想，对于指针运算来说也是非常方便的。

代码实现常见的接口

抽象数据结构定义

假设数组的元素类型为int，那么一个顺序栈的数据成员至少需要三个：

1. 指向堆空间中那块连续内存空间的指针

2. 栈的容量

3. 栈顶指针top

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class SequenceStack {
private:
    friend std::ostream& operator<<(std::ostream& os, const SequenceStack& ss);
    size_t cap_;  // 栈的容量
    int* ptr_;    // 指向栈元素所在的内存空间，栈底
    int top_;     // 指向栈顶
};
std::ostream& operator<<(std::ostream& os, const SequenceStack& ss) {
    // 从栈顶到栈底的顺序输出元素的值
    for (int i = ss.size()-1; i >= 0; --i) {
        std::cout << ss.ptr_[i] << " ";
    }
    std::cout << "\n";
    return os;
}

构造函数

用于定义并初始化一个顺序栈对象：

1. 初始化cap_的值，便于后续申请内存空间

2. 申请cap_个整型元素大小的堆内存空间

3. 初始化栈顶top，将其初始化为0

1
2
3
4

SequenceStack(size_t cap = 10)
    : cap_{cap}
    , ptr_{new int[cap_]{}}
    , top_{0} {}

析构函数

这是拥有动态资源的一个类必须要自定义的函数，主要用于释放动态资源防止资源泄漏。

1
2
3
4

~SequenceStack() {
    delete[] ptr_;
    ptr_ = nullptr;
}

判断栈是否是空栈

由于top的语义是下一个待插入元素的数组索引，那么当这个索引等于0的时候，它就是空栈，因为索引0上暂时都还没有元素，那它就是空栈呀。

1
2

// 栈空
bool empty() const { return top_ == 0; }

判断栈是否是满栈

满栈代表栈中存储了cap_个有效元素，根据左闭右开的区间思想，top - 0就是当前有效元素的个数，若它等于cap_，也就是top == cap，此时栈就是一个满栈。

1
2

// 栈满
bool full() const { return top_ == cap_; }

获取栈顶元素

由于top直线栈顶元素的下一个位置，那么获取栈顶元素的值，需要拿到栈顶元素的索引，那就是top - 1，利用索引就可拿到栈顶元素的值

1
2
3
4
5
6
7
8
9

// 获取栈顶元素
int top()const {
    // 若栈为空
    if (empty()) {
        throw "stack is empty!";
    }
    // 是top_ - 1作为索引，而不是--top_;
    return ptr_[top_ - 1];
}

获取栈内有效元素的个数

top是下一个插入元素的数组索引，那么它的值就是前面有效元素的个数。

1
2

// 栈内有效元素的个数
int size() const { return top_; }

获取栈的容量

直接return cap_即可

1
2

// 获取栈的容量
size_t cap() const { return cap_; }

栈扩容

当栈满的时候，需要进行扩容，由于栈内的元素是整数类型，扩容起来很简单，但是若是元素是自定义类型的话，那么是需要考虑很多性能因素的，能移动绝不拷贝，绝不可能直接使用new，而是使用operator new先申请内存空间，再使用placement new完成构造(若可移动构造保证不会出现异常就移动构造，若可能出现异常就拷贝构造，拷贝的过程中哪怕出现异常，也不影响原内存空间的对象)。

由于这里使用的是整数类型，直接就简单的扩容了

1. 根据新的容量申请新的内存空间

2. 将旧内存空间的数据拷贝到新内存空间

3. 释放旧的内存空间

4. 更新ptr_与cap_的值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// 扩容接口
void expand(size_t new_cap) {
    // 1. 申请的内存空间
    int* tmp = new int[new_cap]{};

    // 2.将原来旧空间的数据拷贝到新空间中
    memcpy(tmp, ptr_, sizeof(int) * cap_);

    // 3. 释放掉原来的旧空间
    delete[] ptr_;

    // 4. 指向新的内存空间，更改容量的大小
    ptr_ = tmp;
    cap_ = new_cap;
}

入栈

1. 判断栈是否满了，若栈满，则扩容

2. 根据上述对满栈、空栈的理解，满栈的入栈思想就是先插入数据，再移动指针

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// 入栈
void push(int val) {
    // 判断栈是否满了
    if (full()) {
        // 扩容
        expand(cap_ * 2);
    }

    /*
     * 入栈：
     * 1. 写入数据
     * 2. 移动栈顶指针 +1
     */
    ptr_[top_++] = val;
}

出栈

1. 判断栈是否空了，若栈空，在这里直接抛出异常，目的是学习出栈的思想

2. 其实就是top本身的值减一即可，使得原来存储栈顶元素的数组索引，变成下一个待插入元素的数组索引，再以后入栈的时候，以新值覆盖旧值的方式完成出栈。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// 出栈
void pop() {
    // 判断栈是否为空
    if (empty()) {
        // 抛出异常
        throw "stack is empty!";
    }

    /*
     * 出栈：
     * 1. 移动栈顶指针 -1
     */
    --top_;
}

综合测试

核心测试就是出栈、入栈、以及扩容后的容量与有效个数是否正确

1. 入栈

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   void test() { // 定义一个数组 int arr[] = {21, 23, 92, 33, 45, 65, 101, 82, 91, 222}; // 定义一个顺序栈 SequenceStack ss{10}; for (auto var : arr) { ss.push(var); } std::cout << ss << std::endl; std::cout << "before expand cap: " << ss.cap() << " " << "size: " << ss.size() << std::endl; // 入栈触发扩容 ss.push(1000); std::cout << ss << std::endl; std::cout << "after expand cap: " << ss.cap() << " " << "size: " << ss.size() << std::endl; }

   查看输出结果

   1 2 3 4 5

   222 91 82 101 65 45 33 92 23 21 before expand cap: 10 size: 10 1000 222 91 82 101 65 45 33 92 23 21 after expand cap: 20 size: 11

2. 出栈

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

   void test() { // 定义一个数组 int arr[] = {21, 23, 92, 33, 45, 65, 101, 82, 91, 222}; // 定义一个顺序栈 SequenceStack ss{10}; for (auto var : arr) { ss.push(var); } std::cout << ss; std::cout << "before expand cap: " << ss.cap() << " " << "size: " << ss.size() << std::endl; std::cout << "\n"; ss.push(1000); std::cout << ss; std::cout << "after expand cap: " << ss.cap() << " " << "size: " << ss.size() << std::endl; // 获取栈顶元素一次，出栈一次 for (int i = 0; i < 3; ++i) { std::cout << "top: " << ss.top() << std::endl; ss.pop(); std::cout << "cap: " << ss.cap() << " " << "size: " << ss.size() << std::endl; } }

   先获取栈顶的元素，随后进行出栈，然后查看此时顺序栈的容量与有效元素的个数

   1 2 3 4 5 6 7 8 9 10 11 12

   222 91 82 101 65 45 33 92 23 21 before expand cap: 10 size: 10 1000 222 91 82 101 65 45 33 92 23 21 after expand cap: 20 size: 11 top: 1000 cap: 20 size: 10 top: 222 cap: 20 size: 9 top: 91 cap: 20 size: 8

链栈

顺序栈内的元素的地址都是连续的，缓存友好，但是其栈满导致扩容，会一定程度影响执行效率，若是对扩容带来的性能损耗有想法，那么可以利用链表来去实现栈，链表的结点都是new出来的，不会有扩容的烦恼，但是它结点不连续，不缓存是不友好的，不过有利有弊，要有取舍。

链栈：基于链表实现的栈，栈内每个元素的地址不是连续的，这也是链表与数组的核心区别。

在学习链表的时候，可根据头插法和尾插法快速构造一个链表，而它们插入元素的顺序与实际链表遍历出来的元素的顺序是不同的。假设有整型数据1,2,3,4,5,6,7,8,9,10，分别以头插法、尾插法按照顺序插入：

从上述图中可以看出

1. 头插法插入，元素在链表中呈现的元素顺序与插入的顺序是相反的，这代表什么？你若是链表实现一个栈，且使用头插法的话，那么你为了符合栈后进先出的特征，那么你就需要将栈顶指针指向链表中第一个有效元素，因为它此时是最后一个入栈的，它必须第一个出去。总结一下就是，若是使用头插法入链栈，那么就必须使用头删出栈，也就是第一个有效元素作为栈顶元素。

2. 尾插法插入，元素在链表中呈现的元素顺序与插入的顺序是一致的，这代表什么呢？你若是使用链表实现一个栈，且使用尾插法的话，那么你为了符合栈后进先出的特征，那么你就需要将栈顶指针指向链表中最后一个元素，因为它此时是最后一个入栈的，它必须是第一个出去。总结一下就是，若是用尾插法入链栈，那么就必须使用尾删出栈，也就是最后一个有效元素作为栈顶元素。

性能问题

若使用头插头删实现一个栈的入栈和出栈，每次出栈和入栈只需要进行简单的指针间的赋值操作即可，时间复杂度O(1)。但是使用尾插尾删实现一个栈的入栈和出栈的话，对于链表的不同形式，看看需要满足什么条件才能达到O(1)。

1. 单向链表：尾插需要遍历找到尾结点，可显式设置一个尾指针，使找到尾结点的时间复杂度是O(1)。但是尾插就必须需要尾删，而尾删不仅需要找到尾结点，还需要找到其前一个结点，还是需要遍历，因此单向链表的尾插尾删不可取。

2. 单向循环链表：与单向链表不同的是，尾结点的next指向的是头结点或者是第一个有效结点，对于解决尾插与尾删没有帮助，其本质还是和单向链表一样，尾插(在不增加尾指针的情况下)和尾删还是都达不到O(1)。

3. 双向链表：尾插需要遍历找到尾结点，这一点可显式增加尾指针来解决，是O(1)。且双向链表中的每个结点的pre保存着前一个结点的地址，无需遍历找到尾结点的前一个结点，也是O(1)。但是内存空间上带来了浪费，最起码是相对于单向链表的头插头删而言，而且还增加了尾指针。

4. 双向循环链表：在有头结点的情况下，头结点的pre指向了尾结点，因此无需显式增加尾指针可找到尾结点，时间复杂度为O(1)。尾删与双向链表一样，也是O(1)。若无头结点，那就是第一个有效结点也可做到这些，一个性质。但是也带来不小的内存空间消耗。

所以，基于尾插和尾删，带有尾指针的双向链表与双向循环链表的尾插和尾删的时间复杂度都是O(1)，带有尾指针的单向链表与单向循环链表依然达不到尾插和尾删都是O(1)。那么，直接在单向链表的基础上，利用头插头删来实现链栈的入栈和出栈，是最好的选择，这两个操作的时间复杂度都是O(1)。而且还是基于最简单的单向链表。

结构设计

链栈，首先它先是链表，我使用单向链表，且是带有头结点的，方便链表操作。其次，我使用栈顶指针top指向链表中第一个有效元素，使其作为栈顶元素。也就是head→next的值，head指向的是头结点，当无有效元素的时候，它也是head→next的值，那就是nullptr，那么栈顶元素也是nullptr。

这样设计的话，那么核心的一些操作大概的思路就是：

1. 链栈空：top == nullptr

2. 链栈是不会满的，除非操作系统中无可用内存

3. 获取链栈栈顶元素：top→data即可获取

4. 链栈出栈：判断是否链栈空，若不空，则删除第一个有效元素，head→next = top→next;delete top;top = head→next;此时top指向原来链表中的第二个有效元素

5. 链栈入栈：无需判断链栈满。new_node→next = top;head→next = new_node;top = new_node;

代码实现常见的接口

抽象数据结构定义

抽象数据结构定义是不会有任何限制的，全凭你的需求去自由发挥，空间和时间需要良好的平衡

比如，在当前的学习中，我很需要知道链栈内的有效元素个数是多少，这个很简单，遍历一下链表即可。但是这样的话，时间复杂度就是O(n)，若是常使用这个接口，那么效率是非常低的，还有什么好的解决方法呢？我就想到在链栈的具体数据结构定义中新增了一个size_成员，只需要在入栈的时候增加1，出栈的时候减少1即可，在获取栈内的有效元素个数的时候，直接返回size_即可，时间复杂度是O(1)。

所以，根据不同的需要去定义不同的抽象数据结构，要灵活，别怕添加东西。

1. head_指向单向链表的头结点

2. top_指向栈顶的元素

3. size_保存当前链栈内的有效元素的个数

4. 重载«运算符

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <cstddef>
#include <iostream>
#include <ostream>

class LinkedStack {
    struct Node {
        Node(int data = 0)
            : data_{data},
              next_{nullptr} {}
        int data_;
        Node* next_;
    };

public:
    friend std::ostream& operator<<(std::ostream& os, const LinkedStack& ls);

private:
    Node* head_;
    Node* top_;
    int size_;
};

std::ostream& operator<<(std::ostream& os, const LinkedStack& ls) {
    LinkedStack::Node* p = ls.top_;

    while (p) {
        os << p->data_ << " -> ";
        p = p->next_;
    }

    os << "nullptr";

    return os;
}

构造函数

1. 创建一个头结点

2. 初始化数据成员

1
2
3
4

LinkedStack()
    : head_{new Node{}}
    , top_{head_->next_}
    , size_{0} {}

析构函数

逐一释放链栈内的结点，包括头结点

1
2
3
4
5
6
7
8
9

~LinkedStack() {
    while (top_ != nullptr) {
        head_->next_ = top_->next_;
        delete top_;
        top_ = head_->next_;
    }

    delete head_;
}

判断链栈是否为空

top_的值若为nullptr，代表链栈内是没有有效元素的

1
2

// 判断链栈是否为空
bool empty() const { return top_ == nullptr; }

链栈有效元素的个数

直接返回size_即可，它保存了链栈内有效元素的个数

1
2

// 获取链栈有效元素的个数
size_t size() const { return size_; }

获取链栈顶元素

1. 先判断链栈是否为空，因为后续要访问top_指向的对象的数据成员，若top_为nullptr，对空指针解引用会引发段错误

2. 返回栈顶指针指向的对象中的data_

1
2
3
4
5
6

// 获取栈顶元素
int top() const {
    // 判断是否栈空
    if (empty()) throw "linked stack is empty!";
    return top_->data_;
}

入栈

1. 创建新的结点

2. 新结点的next指向top_，因为它要称为栈顶结点

3. 头结点的next_指向新结点完成插入

4. 此时，栈顶结点改变了，变成了new_node，那么top_的值需要更新为new_node的地址

5. 将size_的值+1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 入栈 -> 头插
void push(int val) {
    // 定义一个新的结点
    Node* new_node = new Node{val};

    new_node->next_ = top_;
    head_->next_ = new_node;
    top_ = new_node;
    ++size_;
}

出栈

1. 判断链栈是否为空

2. 将头结点的next_指向栈顶结点的下一个结点

3. 释放旧栈顶结点

4. top_指向新的栈顶结点

5. size_减去一

1
2
3
4
5
6
7
8
9

// 出栈 -> 头删
void pop() {
    // 判断是否栈空
    if (top_ == nullptr) throw "linked stack is empty!";
    head_->next_ = top_->next_;
    delete top_;
    top_ = head_->next_;
    --size_;
}

综合测试

测试各个接口的实现是否正确，特别是出栈与入栈

1. 入栈

   1 2 3 4 5 6 7 8 9 10

   void test() { LinkedStack ls; // 入栈三个元素 ls.push(2); ls.push(3); ls.push(4); std::cout << ls << std::endl; }

   查看输出结果：

   1	4 -> 3 -> 2 -> nullptr

   栈顶结点内的数据值也是对的

2. 出栈

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   void test() { LinkedStack ls; // 入栈三个元素 ls.push(2); ls.push(3); ls.push(4); std::cout << ls << std::endl; // 出栈 ls.pop(); ls.pop(); std::cout << ls << std::endl; }

   查看输出结果：

   1 2 3

   4 -> 3 -> 2 -> nullptr 2 -> nullptr

3. 获取栈顶元素以及栈内的有效元素的个数

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

   void test() { LinkedStack ls; // 入栈三个元素 ls.push(2); ls.push(3); ls.push(4); std::cout << ls << std::endl; std::cout << "top: " << ls.top() << std::endl; std::cout << "元素个数: " << ls.size() << std::endl; std::cout << "\n"; // 出栈 ls.pop(); ls.pop(); std::cout << ls << std::endl; std::cout << "top: " << ls.top() << std::endl; std::cout << "元素个数: " << ls.size() << std::endl; }

   查看输出结果：

   1 2 3 4 5 6 7

   4 -> 3 -> 2 -> nullptr top: 4 元素个数: 3 2 -> nullptr top: 2 元素个数: 1