_{王道C++班级参考资料}
——
C语言部分^卷5数据结构
^_节2栈

最新版本V3.0
王道C++团队
COPYRIGHT ⓒ 2021-2024. 王道版权所有

概述

_Gn!

相比较于数组和链表，栈是一种操作受限的线性结构。

这种操作受限体现在：

1. 栈只能在同一端添加、删除以及访问元素（栈顶）

2. 另一端无法执行任何操作（栈底），栈底的元素既不能直接增删，也不能直接访问。

你可以把栈想象成一个杯子，杯底相当于栈底，无法直接进行任何操作。杯口就相当于栈顶，是唯一可以进行添加、删除和访问操作的地方。

在栈中，最先添加到栈中的元素总是最后被删除的，遵循后进先出（LIFO, Last In First Out）的原则。

如下图所示：

栈这种数据结构的基本操作主要包括以下几种：

1. 入栈/压栈(push)：在栈顶添加一个元素，成为新的栈顶元素，其余元素则被压入栈底。时间复杂度O(1)

2. 出栈/弹栈(pop)：删除栈顶元素，下一个元素成为新的栈顶元素。时间复杂度O(1)

3. 访问栈顶元素(peek)：返回栈顶元素的值。时间复杂度O(1)

4. 判空(is_empty)：检查栈中是否有任何元素。时间复杂度O(1)，因为只需要检查一下栈顶元素即可。

说白了，栈仍然还是一个线性数据结构(数组或链表都可以)，只不过在实现时，只需要提供栈顶的增删访问操作罢了。

为什么需要栈？

_Gn!

栈是一种操作受限的线性结构，既然如此，那么为什么非要使用栈呢？直接使用链表或数组不好吗？

使用栈主要有以下好处：

1. 高效率。由于栈的操作仅限于顶部，栈的所有基本操作（push、pop、peek）通常都具有 O(1) 的时间复杂度，这使得栈在性能上非常高效。

2. 简化代码、增强代码可读性。由于操作受限，编程时的考虑因素更少，更容易实现。也有助于写出更清晰、更易于维护的代码。

3. 非常适合用于解决特定问题。在实际的某些应用场景中，如函数调用管理、括号匹配问题、表达式求值、浏览器的前进后退功能等，自然而然地符合"先进后出"的特点，天然就适合使用栈来解决。

总之，虽然链表提供了更多的灵活性，但在需要特定数据访问模式（如LIFO）的场景中，栈的这种“受限”实际上是一种优势。

这说明在数据结构的选择上，关键在于根据具体的应用需求和场景来决定最合适的结构。

栈的实现方式

_Gn!

栈的实现有两种方式：

1. 基于链表实现

2. 基于数组实现

这两种实现方式各有优缺点，总得来说：

1. 如果以一个固定长度的数组来实现栈，实现方式非常简洁，依赖于数组随机访问效率特别高。也不需要额外的空间来存储指针。但缺点是栈大小固定，无法扩容。

2. 如果用一个动态数组来实现栈，栈具有更灵活的容量，同样随机访问效率高且不需要额外空间存储指针。但缺点是，重分配内存可能是一个较大的性能开销，拖慢整体栈的效率。

3. 如果以链表来实现，灵活性比数组更强，且扩容不涉及内存重分配，栈整体性能稳定。但缺点是空间占用更多，需要存储额外的指针。当然，链表实现肯定会更复杂一些，这也算个小毛病。

总的来说：

1. 在已知栈大小限制或不需要频繁调整栈大小时，优先考虑使用固定长度的数组来实现栈，这会提供更好的性能以及更简单的实现以及使用方式。

2. 在栈大小未知或需要频繁调整栈大小时，可以考虑使用动态数组或链表来实现栈，它们的区别是：

   1. 动态数组实现的缺点是如果需要频繁调整大小，那么性能会非常差。所以如果不需要频繁的进行扩容操作，且对性能需求高，则优先选择动态数组实现。而且现代很多高级编程语言（比如C++、Java等）都已提供了现成的动态数组实现。

   2. 如果栈的大小完全不可预测，使用动态数组实现会导致频繁调整大小的操作，那么可以更多的考虑使用链表实现。

在这里，我们就基于链表来实现一下栈，基于数组的实现就留给大家做作业了。

二级指针链式栈的实现

_Gn!

在课堂上，我们就基于链表来实现一个链式栈，同时为了复习巩固二级指针的语法，我们采用二级指针的语法来实现这个链式栈。

链式栈模型

_Gn!

以链表为基础实现一个栈，首先要基于以下结构体：

链式栈模型-结构体

x
1
typedef int ElementType;
2

3
// 栈的基本单元-栈帧的结点类型定义
4
typedef struct node {
5
    ElementType data;
6
    struct node *next;
7
} StackFrame;

一般而言，我可以再定义一个结构体用于表示整个栈，但这里我们直接在main函数中使用以下语句创建一个栈：

xxxxxxxxxx
1
1
StackFrame *stack = NULL; // stack指针指向栈顶,代指整个栈。NULL表示栈为空

也就是说，这个链式栈的模型如下图所示：

于是栈的四个基本操作，就可以变为链表的四个操作：

1. 入栈：也就是头插法在链表中插入一个结点

2. 出栈：删除链表的第一个结点

3. 访问栈顶元素：访问链表的第一个结点

4. 判空：判断链表的第一个结点是不是NULL

设计头文件

_Gn!

我们要做的第一步仍然是编写头文件。我们可以创建一个头文件"linked_stack.h"(链式栈)

参考代码如下：

链式栈-头文件参考代码

x
1
#ifndef LINKED_STACK_H
2
#define LINKED_STACK_H
3

4
#include <stdbool.h>
5
#include <stdio.h>
6
#include <stdlib.h>
7
typedef int ElementType;
8

9
// 栈的基本单元-栈帧的结点类型定义
10
typedef struct node {
11
    ElementType data;
12
    struct node *next;
13
} StackFrame;
14

15
// 入栈/压栈，需要修改栈顶指针所以需要二级指针传参
16
void stack_push(StackFrame **top, ElementType data);
17

18
// 出栈/弹栈，需要修改栈顶指针所以需要二级指针传参
19
ElementType stack_pop(StackFrame **top);
20

21
// 访问栈顶元素, 不需要修改栈顶指针,一级指针就够了
22
ElementType stack_peek(const StackFrame *top);
23

24
// 链式栈判空, 不需要修改栈顶指针,一级指针就够了
25
bool is_empty(const StackFrame *top);
26

27
#endif // !LINKED_STACK_H  15347103862

注意事项：

1. 入栈和出栈的函数需要对传入的栈顶指针做出修改，所以需要传入栈顶指针的二级指针！！

2. 访问和判空则不需要修改栈帧指针，直接传入指针即可。可以使用const修饰它，这是一个好习惯。

实现判空

_Gn!

判空是最容易实现的，而且判空对后续操作会有影响，所以我们可以最先实现它。参考代码如下：

实现判空-参考代码

x
1
// 链式栈判空
2
bool is_empty(const StackFrame *top) {
3
    return top == NULL;
4
}

只要栈顶指针为空指针，就表示这个链式栈为空，此时就无法进行出栈/访问栈顶元素这样的操作了。

实现入栈

_Gn!

所谓入栈，也就是在链表的头部，使用头插法插入一个结点。这个逻辑我们之前已经写过了，这里只需要注意二级指针的处理就可以了，参考代码如下：

实现入栈-参考代码

x
1
// 入栈/压栈 也就是链表的头插法
2
void stack_push(StackFrame **top, ElementType data) {
3
    // 1.创建新的栈帧
4
    StackFrame *new_frame = malloc(sizeof(StackFrame));
5
    if (new_frame == NULL) {
6
        printf("malloc failed in stack_push.\n");
7
        exit(1);
8
    }
9

10
    // 2.初始化这个新栈帧
11
    new_frame->data = data;
12
    new_frame->next = *top;
13

14
    // 3.更新栈顶指针
15
    *top = new_frame;
16
}

注意二级指针解引用一次可以用于修改原本实参的一级指针。

实现出栈

_Gn!

所谓出栈，也就是根据头指针删除链表的第一个结点。这个逻辑我们也很熟悉了，参考代码如下：

实现出栈-参考代码

x
1
// 出栈/弹栈，也就是在链表头部删除一个结点
2
ElementType stack_pop(StackFrame **top) {
3
    // 1.对栈判空,如果栈顶有元素,才进行出栈操作
4
    if (is_empty(*top)) {
5
        // 栈为空
6
        printf("error: stack is empty.\n");
7
        exit(-1);
8
    }
9
    // 2.先用一个临时指针保存栈顶元素的next栈帧
10
    StackFrame *tmp = *top;
11

12
    // 3.更新栈顶指针
13
    *top = tmp->next;
14
    // 4.将栈顶元素保存以作为返回值
15
    ElementType ret = tmp->data;
16
    // 4.free栈顶元素
17
    free(tmp);
18
    return ret;
19
}

注意，要先判空再执行出栈操作，否则会因解引用空指针导致错误。

实现访问栈顶元素

_Gn!

访问栈顶元素再简单不过了。参考代码如下：

实现访问栈顶元素-参考代码

x
1
// 访问栈顶元素
2
ElementType stack_peek(const StackFrame *top) {
3
    // 对栈判空,如果栈顶有元素,才进行出栈操作
4
    if (is_empty(top)) {
5
        // 栈为空,没有栈顶元素可以访问
6
        printf("error: stack is empty.\n");
7
        exit(-1);
8
    }
9
    return top->data;
10
}

仍然要注意先判空，才能解引用。

补充: 不使用二级指针的链式栈

_Gn!

上述代码实现栈，主要目的是为了练习二级指针的语法，为了更方便的使用栈，我们一般还是选择基于以下声明定义来实现栈：

链式栈的实现-参考头文件

x
1
#ifndef LINKED_STACK_H
2
#define LINKED_STACK_H
3
#include <stdbool.h>
4
#include <stdio.h>
5
#include <stdlib.h>
6

7
typedef int ElementType;
8

9
// 栈的一个结点栈帧,类型定义
10
typedef struct node_s {
11
    ElementType data;
12
    struct node_s *next;
13
}StackFrame;    
14

15
typedef struct {
16
    StackFrame *top;    // 栈顶指针
17
}LinkedStack;
18

19
// 基本操作
20
// 创建链式栈
21
LinkedStack *stack_create();
22
// 销毁链式栈
23
void stack_destroy(LinkedStack *stack);
24
// 判空
25
bool is_empty(LinkedStack *stack);
26
// 入栈
27
void stack_push(LinkedStack *stack, ElementType data);
28
// 出栈并返回栈顶元素
29
ElementType stack_pop(LinkedStack *stack);
30
// 访问栈顶元素
31
ElementType stack_peek(LinkedStack *stack);
32

33
#endif // !LINKED_STACK_H

这些函数的实现可以参考以下代码：

链式栈的实现-参考实现源文件

x
1
#include "linked_stack.h"
2

3
// 新建一个空栈
4
LinkedStack *stack_create() {
5
    // callock可以不用手动初始化空指针
6
    return calloc(1, sizeof(LinkedStack));
7
}
8
// 对于链式栈而言，销毁栈就是销毁链表
9
void stack_destroy(LinkedStack *stack) {
10
    // 相当于遍历链表(出栈)然后在遍历中逐个free结点
11
    StackFrame *curr = stack->top;
12
    while (curr != NULL) {
13
        StackFrame *tmp = curr->next;   // 保存后继结点
14
        free(curr);
15
        curr = tmp;
16
    }
17
    // 最后free栈结构体
18
    free(stack);
19
}
20

21
bool is_empty(LinkedStack *stack) {
22
    return stack->top == NULL;
23
}
24

25
// 相当于链表头插法插入结点，栈顶指针相当于链表的头指针
26
void stack_push(LinkedStack *stack, ElementType data) {
27
    // 1.新建一个栈帧结点
28
    StackFrame *new_frame = malloc(sizeof(StackFrame));
29
    if (new_frame == NULL) {
30
        printf("malloc failed in stack_push.\n");
31
        exit(1);
32
    }
33
    // 2.初始化新栈帧
34
    new_frame->data = data;
35
    new_frame->next = stack->top;
36
    // 3.更新栈顶指针
37
    stack->top = new_frame;
38
}
39

40
// 相当于链表在头部删除第一个结点,栈顶指针相当于链表的头指针
41
ElementType stack_pop(LinkedStack *stack) {
42
    // 1.栈判空处理
43
    if (is_empty(stack)) {
44
        printf("error: stack is empty.\n");
45
        exit(1);
46
    }
47
    // 2.出栈返回栈顶元素,并free结点,更新栈顶指针
48
    StackFrame *curr = stack->top;
49
    ElementType data = curr->data;
50
    stack->top = curr->next;
51
    free(curr);
52
    return data;
53
}
54
ElementType stack_peek(LinkedStack *stack) {
55
    if (is_empty(stack)) {
56
        printf("error: stack is empty.\n");
57
        exit(1);
58
    }
59
    return stack->top->data;
60
}

以上。

补充: 动态数组栈

_Gn!

基于动态数组，我们也完全可以实现一个可以自动扩容的动态数组栈。首先基于以下头文件：

动态数组栈头文件-参考代码

x
1
#ifndef DYNAMIC_STACK_H
2
#define DYNAMIC_STACK_H
3
#include <stdio.h>
4
#include <stdlib.h>
5
#include <stdbool.h>
6

7
typedef int ElementType;
8

9
typedef struct {
10
    ElementType *elements;   // 指向动态数组首元素的指针
11
    int size;   // 元素的个数
12
    int capacity; // 数组的容量，也就是栈的容量
13
} DynamicStack;
14

15
// 创建动态数组栈
16
DynamicStack *stack_create();
17
// 销毁动态数组栈
18
void stack_destroy(DynamicStack *s);
19
// 入栈
20
void stack_push(DynamicStack *s, ElementType val);
21
// 出栈并返回栈顶元素
22
ElementType stack_pop(DynamicStack *s);
23
// 访问栈顶元素
24
ElementType  stack_peek(DynamicStack *s);
25
// 判空
26
bool is_empty(DynamicStack *s);
27

28
#endif // !DYNAMIC_ARR_STACK_H

这些函数的实现可以参考以下代码：

动态数组栈实现-参考代码

x
1
#include "dynamic_stack.h"
2
#define DEFAULT_CAPACITY 8  // 动态栈的默认容量
3
#define THRESHOLD 1024  // 扩容阈值
4

5
// 实现扩容机制
6
static void grow_capacity(DynamicStack *s) {
7
    // 扩容策略: 超过阈值则1.5倍的扩容，否则2倍的扩容
8
    int new_capacity = (s->capacity >= THRESHOLD) ?
9
        (s->capacity + (s->capacity >> 1)) :
10
    (s->capacity << 1);
11

12
    // 使用realloc函数实现扩容，重新分配内存
13
    ElementType *new_arr = realloc(s->elements, new_capacity * sizeof(ElementType));
14
    if (new_arr == NULL) {
15
        printf("Error: realloc failed in grow_capacity\n");
16
        exit(1);
17
    }
18
    // 更新动态数组栈结构体的信息
19
    s->elements = new_arr;
20
    s->capacity = new_capacity;
21
}
22
// 创建一个动态数组栈
23
DynamicStack *stack_create() {
24
    DynamicStack *s = malloc(sizeof(DynamicStack));
25
    if (s == NULL) {
26
        printf("malloc failed in stack_create.\n");
27
        return NULL;
28
    }
29
    // 初始化动态数组  
30
    s->size = 0;
31
    s->capacity = DEFAULT_CAPACITY;
32
    s->elements = malloc(DEFAULT_CAPACITY * sizeof(ElementType));
33
    if (s->elements == NULL) {
34
        free(s);
35
        printf("malloc failed in stack_create.\n");
36
        return NULL;
37
    }
38
    return s;
39
}
40
// 销毁一个栈
41
void stack_destroy(DynamicStack *s) {
42
    // 先释放动态数组
43
    free(s->elements);
44
    // 再释放栈结构体
45
    free(s);
46
}
47

48
// 将数组末尾视为栈顶，将size属性作为新插入结点的下标，这就是入栈
49
void stack_push(DynamicStack *s, ElementType val) {
50
    if (s->capacity == s->size) {
51
        // 栈满了,需要扩容
52
        grow_capacity(s);
53
    }
54

55
    // 可以直接把size作为入栈出栈的操作索引
56
    s->elements[s->size] = val;
57
    s->size++;
58
    // 上面的两行代码可以合并成一行
59
    // s->elements[s->size++] = val;
60
}
61

62
// 将数组末尾视为栈顶，将size属性减1，这就是出栈。元素取值并不用改变
63
ElementType stack_pop(DynamicStack *s) {
64
    if (is_empty(s)) {
65
        printf("Error: stack is empty\n");
66
        exit(1);
67
    }
68
    s->size--;
69
    return s->elements[s->size];
70

71
    // 上面的两行代码可以合并成一行
72
    // return s->elements[--(s->size)];
73
}
74
// 访问栈顶元素
75
ElementType stack_peek(DynamicStack *s) {
76
    if (is_empty(s)) {
77
        printf("Error: stack is empty\n");
78
        exit(1);
79
    }
80
    return s->elements[s->size - 1];
81
}
82
// 判空
83
bool is_empty(DynamicStack *s) {
84
    return s->size == 0;
85
}

写完这些实现，可以写一个测试用例来测试这个动态栈。如下：

动态栈-测试用例代码

x
1
#include "dynamic_stack.h"
2

3
int main(void) {
4
    DynamicStack *s = stack_create();
5
    // 入队列1000个元素
6
    for (int i = 0; i < 1000; i++) {
7
        stack_push(s, i);
8
    }
9
    // 出队列直到队列为空
10
    while (!is_empty(s)) {
11
        ElementType ele = stack_peek(s);
12
        printf("%d ", ele); // 预期会将999-0倒着输出打印
13
        stack_pop(s);
14
    }
15
    printf("\n");
16
    // 再次尝试出栈, 此时会打印错误提示信息
17
    stack_pop(s);
18
    // 销毁队列
19
    stack_destroy(s);
20

21
    return 0;
22
}

此动态数组栈会将0~999顺序存进栈中，再遍历出栈时，遵循"先进后出"的原则，此段代码会将999- 0，倒着输出出来。

栈的应用场景

_Gn!

栈特别适用那些存在"后进先出"逻辑的场景，在实际的开发，栈很常用。栈至少可以应用于以下领域：

1. 函数调用机制

2. 括号匹配问题

3. 表达式求值问题

4. 浏览器历史记录前进后退功能

5. 深度优先遍历算法（一般直接用函数调用者递归实现）

6. ...

函数调用机制

_Gn!

在编程语言当中，函数(方法)的调用机制都要依赖于栈的"后进先出"机制，这是程序员日常接触到最常见的栈的应用场景。

稍微要注意的是，编程语言中函数调用栈，是编程语言以及计算机硬件共同管理维护的，这个过程程序员一般是不可控自动完成的，不能就简单的将函数调用栈等同于数据结构里的栈。

但是好在，它们的共同特点是"后进先出"，对于普通的程序员而言，只需要：

1. 就把函数调用简单的理解成："函数栈帧进栈，成为栈顶元素"

2. 把函数执行结束理解成："栈顶的函数栈帧出栈销毁"

这样就可以了。

知道这些，对于理解一门编程语言的函数调用过程，理解程序的执行流程是足够的。

括号匹配问题

_Gn!

如果仅仅是某一种括号(比如小括号)的匹配，那只需要写一个循环遍历字符串即可求解匹配问题。但如果是多种类型的括号同时存在一个字符串中，比如：

1. {[()]}：匹配成功

2. ()[]{}：匹配成功

3. [{()}]：匹配成功

4. [({}]：匹配失败

5. [()]{：匹配失败

6. ...

单靠循环求解就非常困难了。这时我们就可以考虑使用栈这种数据结构来求解。怎么思考这个问题呢？

栈的核心操作是入栈和出栈，这和括号匹配有啥关系呢？

很简单按照下列思路就可以了：

1. 遍历整个字符串

2. 遇到任意左括号，就将它的对应右括号入栈

3. 遇到任意右括号：

   1. 先判断当前栈是否为空，如果栈为空说明括号匹配失败

   2. 在栈不为空的前提下，立刻将当前栈顶元素出栈，判断栈顶元素是否和该右括号是同类型右括号

      • 如果不是，说明括号匹配失败

      • 如果是同类型右括号，那就继续遍历字符串重复上面的操作。

4. 如果遍历完字符串，发现栈也同时为空，说明匹配括号成功。如果发现栈中还有残留的右括号，那么说明匹配失败。

我们使用上面已经实现的一个链式栈来辅助完成，参考的代码实现如下：

括号匹配问题C语言实现-参考代码

x
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3
#include <stdlib.h>
4
#include <ctype.h>
5
#include <stdbool.h>
6
#include "linked_stack.h"   // 已实现的链式栈
7

8
char get_right_bracket(char ch) {
9
    switch (ch) {
10
        case '{': return '}';
11
        case '[': return ']';
12
        case '(': return ')';
13
        default: return 0;
14
    }
15
}
16
bool is_left_bracket(char ch) {
17
    return ch == '{'
18
        || ch == '['
19
        || ch == '(';
20
}
21

22
bool is_right_bracket(char ch) {
23
    return ch == '}'
24
        || ch == ']'
25
        || ch == ')';
26
}
27

28
bool is_matching(char *str, LinkedStack *stack) {
29
    while (*str) {
30
        // 排除非括号字符
31
        if (is_left_bracket(*str)) {
32
            // 字符是左括号,于是将它对应的右括号入栈
33
            char right_bracket = get_right_bracket(*str);
34
            stack_push(stack, right_bracket);
35
        }
36
        if (is_right_bracket(*str)) {
37
            // 如果遇到右括号时栈为空,说明右括号在前面,匹配失败
38
            // 如果栈不为空就出栈,和当前字符比较,如果不一致就匹配失败
39
            if (is_empty(stack) || stack_pop(stack) != *str) {
40
                return false;
41
            }
42
        }
43
        str++;
44
    }
45
    // 字符串遍历完成,判断栈是否空
46
    return is_empty(stack);
47
}
48

49
int main(void) {
50
    LinkedStack *stack = stack_create();
51
    char *str = "1()23{[}";
52
    if (is_matching(str, stack)) {
53
        printf("匹配成功!\n");
54
    }
55
    else {
56
        printf("匹配失败!\n");
57
    }
58
    stack_destroy(stack);
59
    return 0;
60
}

若传入的字符串不包含括号，此函数也会返回true，没有括号那也算是匹配成功吧。

表达式求值

_Gn!

表达式求值对于任何编程语言而言都是基础逻辑，这个过程一般发生在程序的运行期间。

程序员在代码中输入的表达式，一般被我们称之为"中缀表达式"，也就是我们日常生活、数学中使用的表达式，指的是将运算符放在操作数中间的一种表达式，如：

1. A + B

2. 7 * 3

3. (1 + 2) * (3 - 4)

4. ..

中缀表达式的主要特点是它们对于人类来说非常直观，但如果让计算机直接处理中缀表达式的求值，就意味着需要像人类一样考虑优先级和括号等问题，实现起来就太麻烦了，一般计算机都不会直接处理中缀表达式。

为了能够在计算机中更轻松的处理表达式求值，普遍会先把中缀表达式处理成"后缀表达式"，也就是一种将运算符放在操作数后面的表达式形式，如：

1. A B + 等价于 A + B

2. 7 3 * 等价于 7 * 3

3. 1 2 + 3 4 - * 等价于 (1 + 2) * (3 - 4)

4. ...

后缀表达式虽然对于人类来说不是特别直观比较容易摸不到头脑，但对于计算机而言，进行一些特殊处理，可以很容易很轻松地进行表达式求值运算。

总之，在计算机内部处理表达式求值问题时，往往会存在两个过程：

1. 将中缀表达式处理成后缀表达式

2. 利用后缀表达式计算求值

而这两个过程，大多都会选择使用栈来辅助完成，利用栈的"后进先出"的特点。

转换成后缀表达式

_Gn!

中缀表达式转换成后缀表达式的过程，需要一个运算符栈来辅助完成，大致过程思路如下：

1. 从左往右遍历中缀表达式：

2. 如果遇到操作数：直接将其添加到结果后缀表达式中，不进栈。

3. 如果遇到操作符（如 +, -, *, /），那么就比较当前遍历到的运算符与运算符栈顶的运算符的优先级：

   1. 如果当前运算符的优先级高于栈顶运算符的优先级，或者栈为空，则将当前运算符压入栈中。

   2. 如果当前运算符的优先级低于或等于栈顶运算符的优先级，则需要将栈顶的运算符弹栈并添加到后缀表达式中，然后再次比较新的栈顶运算符与当前操作符的优先级。这一过程持续进行，直到当前运算符可以被压入栈中。

   3. 如果当前栈顶是一个左括号，那么不论是什么运算符，都直接将运算符入栈。

4. 如果遇到左括号(：立刻将它压入运算符栈。

5. 如果遇到右括号 )：立刻将运算符栈中的运算符弹栈并输出到后缀表达式中，这个过程会持续到遇到左括号为止。但不会将左括号添加到后缀表达式中，只是从运算符栈中移除它。且也不会把右括号添加到后缀表达式中，后缀表达式中不存在小括号。

6. 遍历完中缀表达式后，若运算符栈中还剩余运算符，则将这些运算符依次弹栈，添加到后缀表达式中。

7. 得到最终的后缀表达式结果。

举个例子，将中缀表达式 2 * (3 + 4) / 2 - 2 转换为后缀表达式：

1. 扫描到 2，它是操作数，所以添加到结果后缀表达式：2

2. 扫描到 *，此时栈为空，压入运算符栈：栈内为 *(左边表示栈顶)

3. 扫描到 (，遇到左小括号立刻压入操作符栈：栈内为 ( *

4. 扫描到 3，它是操作数，添加到后缀表达式：2 3

5. 扫描到 +，当前栈顶是左小括号，直接将加号压入运算符栈：栈内为 + ( *

6. 扫描到 4，添加到后缀表达式：2 3 4

7. 扫描到 )，弹出栈内操作符直到遇到 (：后缀表达式变为 2 3 4 +，栈内为 *

8. 扫描到 /，由于其优先级与栈顶的 * 相同，根据左结合性，弹出 * 并加入后缀表达式，然后将 / 压入栈：后缀表达式为 2 3 4 + *，栈内为 /

9. 扫描到 2，添加到后缀表达式：2 3 4 + * 2

10. 扫描到 -，它的优先级不如栈顶的/，于是将/出栈加入后缀表达式中，并让-入栈。此时后缀表达式是2 3 4 + * 2 /，栈内为：-

11. 最后扫描到2，它是操作数，直接添加到后缀表达式中2 3 4 + * 2 / 2。

12. 最后，弹出栈内剩余的操作符并添加到后缀表达式：2 3 4 + * 2 / 2 -

现在你已经得到了一个后缀表达式，那么接下来我们仍然可以利用栈来计算这个后缀表达式。

下列是利用C语言代码实现，中缀表达式转换为中缀表达式的过程。只考虑"+ - * /"四种运算符以及"()"，只考虑整数运算。

代码实现如下：

转换后缀表达式-参考代码

xxxxxxxxxx
1
130
1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <ctype.h>
4
#include <string.h>
5

6
#define MAX_LEN 100  // 定义栈的最大容量
7

8
// 定义操作符栈，进出栈的都是操作符字符
9
typedef struct {
10
    int top;          // 栈顶下标
11
    char ops[MAX_LEN];  // 用于操作符进出栈的数组
12
} OperatorStack;
13

14
// 初始化栈
15
void init_stack(OperatorStack *s) {
16
    s->top = -1;  // 初始化栈顶索引为-1，表示栈为空
17
}
18

19
// 检查栈是否为空
20
int is_empty(const OperatorStack *s) {
21
    return s->top == -1;
22
}
23

24
// 检查栈是否已满
25
int is_full(const OperatorStack *s) {
26
    return s->top == MAX_LEN - 1;
27
}
28

29
// 压栈操作
30
void push(OperatorStack *s, char op) {
31
    if (!is_full(s)) {
32
        s->top++;           // 栈顶指针先上移
33
        s->ops[s->top] = op;  // 将操作符压入栈顶
34
    }
35
    else {
36
        printf("error: Stack is full!\n");  // 栈满时的警告
37
    }
38
}
39

40
// 出栈操作
41
char pop(OperatorStack *s) {
42
    if (!is_empty(s)) {
43
        char op = s->ops[s->top];  // 获取栈顶元素
44
        s->top--;                   // 栈顶指针下移
45
        return op;
46
    }
47
    else {
48
        printf("error: Stack is empty!\n");  // 栈空时的警告
49
        return '\0';  // 返回空字符作为错误提示
50
    }
51
}
52

53
// 查看栈顶元素但不移除
54
char peek(const OperatorStack *s) {
55
    if (!is_empty(s)) {
56
        return s->ops[s->top];  // 返回栈顶元素
57
    }
58
    else {
59
        return '\0';  // 栈空时返回空字符
60
    }
61
}
62

63
// 判断字符是否为运算符
64
int is_operator(char ch) {
65
    return ch == '+' || ch == '-' || ch == '*' || ch == '/';
66
}
67

68
// 运算符优先级判断
69
int precedence(char op) {
70
    switch (op) {
71
    case '+':
72
    case '-':
73
        return 1;  // 低优先级
74
    case '*':
75
    case '/':
76
        return 2;  // 高优先级
77
    default:
78
        return 0;
79
    }
80
}
81

82
// 中缀表达式转后缀表达式
83
void infix_to_postfix(const char *infix, char *postfix) {
84
    OperatorStack s;
85
    init_stack(&s);
86
    int i = 0, j = 0;
87
    char ch;
88

89
    while ((ch = infix[i++]) != '\0') {
90
        if (isdigit(ch)) {  // 如果是数字，直接添加到后缀表达式
91
            postfix[j++] = ch;
92
        }
93
        else if (ch == '(') {
94
            push(&s, ch);  // 左括号压栈
95
        }
96
        else if (ch == ')') {
97
            // 遇到右括号，弹出元素直到左括号
98
            while (!is_empty(&s) && peek(&s) != '(') {
99
                postfix[j++] = pop(&s);
100
            }
101
            pop(&s);  // 弹出左括号，不加入到后缀表达式
102
        }
103
        else if (is_operator(ch)) {
104
            // 遇到运算符，弹出所有优先级高于或等于当前运算符的栈顶元素
105
            while (!is_empty(&s) && precedence(ch) <= precedence(peek(&s))) {
106
                postfix[j++] = pop(&s);
107
            }
108
            push(&s, ch);  // 压入当前运算符
109
        }
110
    }
111

112
    // 将栈中剩余的运算符加入到后缀表达式
113
    while (!is_empty(&s)) {
114
        postfix[j++] = pop(&s);
115
    }
116
    postfix[j] = '\0';  // 结尾添加字符串终止符
117
}
118

119
// 主函数
120
int main() {
121
    char infix[] = "2 * (3 + 4) / 2 - 2";
122
    char postfix[MAX_LEN];
123

124
    infix_to_postfix(infix, postfix);
125
    printf("中缀表达式是: %s\n", infix);           // 输出中缀表达式
126
    printf("对应后缀表达式是: %s\n", postfix);       // 输出后缀表达式
127

128
    return 0;
129
}

简单了解一下即可。

后缀表达式求值

_Gn!

后缀表达式求值也需要利用栈结构来辅助完成，这个过程会更简单一些：

1. 从左往右遍历中缀表达式：

2. 如果遇到操作数：直接将其压入栈中。

3. 如果遇到运算符：

   1. 从栈中弹出所需数量的操作数，执行相应的运算，然后将结果压回栈中。比如对于二元操作符（如 +, -, *, /），需要弹出两个操作数。

   2. 注意：对于-或/这样在意操作数前后的二元运算符来说，假如此时栈中的两个操作数是a b(左边表示栈顶)，那么它们运算规则应该是b - a。（思考一下这是为什么？）

4. 重复此过程，直到整个表达式被扫描完毕。

5. 表达式的结果就是栈顶数值。

比如我们上面已经得到的一个后缀表达式2 3 4 + * 2 / 2 -，利用栈，其计算过程和结果是：

1. 前三个扫描到的都是操作数，于是都直接入栈。栈中元素是：4 3 2(左边表示栈顶)

2. 扫描到+，于是将栈顶的两个操作数出栈(因为加法是二元运算符)，于是计算3 + 4结果是7，将7存入栈顶。栈中元素目前是：7 2

3. 继续扫描到*，于是将栈顶的两个操作数出栈(因为乘法是二元运算符)，于是计算2 * 7结果是14，将14存入栈顶。栈中元素目前是：14

4. 继续扫描到2，它是一个操作数，于是直接入栈。栈中元素目前是：2 14

5. 继续扫描到/，于是将栈顶的两个操作数出栈(因为除法是二元运算符)，于是计算14 / 2结果是7，将它入栈。此时栈中元素是：7

6. 继续扫描到2，它是一个操作数，于是直接入栈。栈中元素目前是：2 7

7. 继续扫描到-，于是将栈顶的两个操作数出栈(因为减法是二元运算符)，于是计算7 - 2结果是5，将它入栈。此时栈中元素是：5

8. 发现后缀表达式扫描完成，于是此时的栈顶元素5，就是表达式的最终结果。

同样基于一个操作数栈，可以实现后缀表达式求值，只考虑"+ - * /"四种运算符以及"()"，只考虑整数运算。参考代码如下：

xxxxxxxxxx
1
114
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3
#include <stdlib.h>
4
#include <ctype.h>  // 用于isdigit函数
5

6
#define MAX_LEN 100  // 定义栈的最大容量
7

8
// 定义操作数栈,进出栈的都是后缀表达式的操作数
9
typedef struct {
10
    int top;    // 栈顶索引
11
    int values[MAX_LEN];    // 操作数进出栈的数组
12
} ValueStack;
13

14
// 初始化操作数栈
15
void init_stack(ValueStack *s) {
16
    s->top = -1;
17
}
18

19
// 检查栈是否为空
20
int is_empty(const ValueStack *s) {
21
    return s->top == -1;
22
}
23

24
// 检查栈是否已满
25
int is_full(const ValueStack *s) {
26
    return s->top == MAX_LEN - 1;
27
}
28

29
// 压栈操作
30
void push_value(ValueStack *s, int value) {
31
    if (!is_full(s)) {
32
        s->top += 1;  // 先增加栈顶索引
33
        s->values[s->top] = value;  // 将整数值压入栈顶
34
    }
35
    else {
36
        printf("error: value stack is full!\n");
37
    }
38
}
39

40
// 出栈操作
41
int pop_value(ValueStack *s) {
42
    if (!is_empty(s)) {
43
        int value = s->values[s->top];  // 获取栈顶元素
44
        s->top -= 1;  // 栈顶索引减少
45
        return value;
46
    }
47
    else {
48
        printf("error: value stack is empty, cannot pop!\n");  // 栈空时输出错误信息
49
        return 0;  // 返回0作为错误情况的默认值
50
    }
51
}
52

53
// 查看栈顶元素但不移除
54
int peek_value(ValueStack *s) {
55
    if (!is_empty(s)) {
56
        return s->values[s->top];  // 返回栈顶元素
57
    }
58
    else {
59
        printf("error: value stack is empty, cannot peek!\n");
60
        return 0;  // 栈为空时的错误处理，返回0
61
    }
62
}
63

64
// 执行运算
65
int evaluate(int val1, int val2, char operator) {
66
    switch (operator) {
67
    case '+': return val1 + val2;
68
    case '-': return val1 - val2;
69
    case '*': return val1 * val2;
70
    case '/': return val1 / val2;
71
    default:  return 0;  // 对于非法运算符返回0
72
    }
73
}
74

75
// 后缀表达式求值
76
int evaluate_postfix(const char *postfix) {
77
    ValueStack s;          // 声明一个操作数栈
78
    init_stack(&s);        // 初始化栈，确保开始时栈是空的
79
    int i = 0;             // 字符串遍历索引
80
    char ch;               // 用于存储当前遍历到的字符
81

82
    // 遍历后缀表达式字符串直到遇到字符串结束符 '\0'
83
    while ((ch = postfix[i]) != '\0') {
84
        if (isdigit(ch)) {
85
            // 如果当前字符是数字，则将其转换为整数并压入栈中
86
            // '0'的ASCII码值用于从字符转换到相应的整数值
87
            push_value(&s, ch - '0');
88
        }
89
        else if (ch == ' ' || ch == '\t') {
90
            // 如果遇到空格或制表符，则跳过，继续遍历
91
            // 这些字符在后缀表达式中用于分隔数字和运算符
92
        }
93
        else {
94
            // 如果当前字符是运算符，则需要从栈中弹出两个操作数进行计算
95
            int val2 = pop_value(&s);  // 弹出第一个操作数（右操作数）
96
            int val1 = pop_value(&s);  // 弹出第二个操作数（左操作数）
97
            int result = evaluate(val1, val2, ch);  // 根据运算符计算结果
98
            push_value(&s, result);  // 将计算结果压回栈中
99
        }
100
        i++;  // 移动索引到下一个字符
101
    }
102

103
    // 循环结束后，栈顶元素是整个后缀表达式的计算结果
104
    return pop_value(&s);  // 弹出并返回最终结果
105
}
106

107
// 主函数，用于测试
108
int main() {
109
    char postfix_exp[] = "2 3 4 + * 2 / 2 -";
110
    int result = evaluate_postfix(postfix_exp);
111
    printf("待计算的后缀表达式是 '%s' ，计算的结果是: %d\n", postfix_exp, result);
112
    return 0;
113
}

总结

以上，我们就通过栈这种数据结构，解决了计算机内的表达式求解问题。当然实际情况，由于运算符更多，需要考虑的优先级也更多，会更复杂一些，但逻辑上是完全没有问题的。

浏览器历史前进后退功能

_Gn!

浏览器历史的前进后退功能，看起来很强大的功能，实际上只需要两个栈就可以实现了：

1. 一个前进栈，用于存储用户在点击后退按钮后，再点击前进按钮可能访问的页面。最初是空的。

2. 一个后退栈，用于指示存储用户当前访问的页面，以及用户的历史访问页面记录以用作实现后退按钮。

具体来说是：

1. 访问新页面：当用户访问一个新页面时，将新访问的当前页面压入后退栈中，并立刻清空前进栈。后退栈的栈顶始终表示当前正在访问的页面。

2. 后退按钮：当用户点击浏览器的后退按钮时，后退栈弹栈，并且将弹出的页面压入前进栈。后退栈弹栈后，后退栈栈顶下的一个页面就成为了新的当前页面。

3. 前进按钮：前进按钮仅在前进栈不为空时生效。当用户点击浏览器的前进按钮时，前进栈弹栈，并且将弹出的页面压入后退栈。此时前进栈弹出的页面就成为了后退栈的栈顶，也就成为了新的当前页面。

可以画图来理解这个过程：

这种使用两个栈的方法非常适合处理线性的浏览历史，因为它自然地模拟了后退和前进操作的LIFO（后进先出）特性。此外，它也使得浏览器能够快速访问历史记录，无需遍历整个历史列表。

栈在浏览器前进后退功能的应用，充分体现了栈可以用于记录"轨迹"的作用，在算法思想中有一种叫做"回溯"的思想，它就是利用了栈的这个特点。

The End