c#栈及其应用
栈
相比较于数组和链表，栈是一种操作受限的线性结构。
这种操作受限体现在：
- 栈只能在同一端添加、删除以及访问元素（栈顶）
- 另一端无法执行任何操作（栈底），栈底的元素既不能直接增删，也不能直接访问。
在栈中，最先添加到栈中的元素总是最后被删除的，遵循后进先出（LIFO, Last In First Out）的原则。在栈顶操作。
栈这种数据结构的基本操作主要包括以下几种：
- 入栈/压栈(push)：在栈顶添加一个元素，成为新的栈顶元素，其余元素则被压入栈底。时间复杂度O(1)
- 出栈/弹栈(pop)：删除栈顶元素，下一个元素成为新的栈顶元素。时间复杂度O(1)
- 访问栈顶元素(peek)：返回栈顶元素的值。时间复杂度O(1)
- 判空(is_empty)：检查栈中是否有任何元素。时间复杂度O(1)，因为只需要检查一下栈顶元素即可。
栈仍然还是一个线性数据结构(数组或链表都可以)，只不过在实现时，只需要提供栈顶的增删访问操作罢了。
栈的实现方式
栈的实现有两种方式：
- 基于链表实现
- 基于数组实现
这两种实现方式各有优缺点，总得来说：
- 如果以一个固定长度的数组来实现栈，实现方式非常简洁，依赖于数组随机访问效率特别高。也不需要额外的空间来存储指针。但缺点是栈大小固定，无法扩容。
- 如果用一个动态数组来实现栈，栈具有更灵活的容量，同样随机访问效率高且不需要额外空间存储指针。但缺点是，重分配内存可能是一个较大的性能开销，拖慢整体栈的效率。
- 如果以链表来实现，灵活性比数组更强，且扩容不涉及内存重分配，栈整体性能稳定。但缺点是空间占用更多，需要存储额外的指针。当然，链表实现肯定会更复杂一些，这也算个小毛病。
总的来说：
- 在已知栈大小限制或不需要频繁调整栈大小时，优先考虑使用固定长度的数组来实现栈，这会提供更好的性能以及更简单的实现以及使用方式。
在栈大小未知或需要频繁调整栈大小时，可以考虑使用动态数组或链表来实现栈，它们的区别是：
- 动态数组实现的缺点是如果需要频繁调整大小，那么性能会非常差。所以如果不需要频繁的进行扩容操作，且对性能需求高，则优先选择动态数组实现。而且现代很多高级编程语言（比如C++、Java等）都已提供了现成的动态数组实现。
- 如果栈的大小完全不可预测，使用动态数组实现会导致频繁调整大小的操作，那么可以更多的考虑使用链表实现。
链式栈模型
以链表为基础实现一个栈，首先要基于以下结构体：
typedef int ElementType;// 栈的基本单元-栈帧的结点类型定义 typedef struct node {ElementType data;struct node *next; } StackFrame;一般而言，我可以再定义一个结构体用于表示整个栈，但这里我们直接在main函数中使用以下语句创建一个栈：
StackFrame *stack = NULL; // stack指针指向栈顶,代指整个栈。NULL表示栈为空于是栈的四个基本操作，就可以变为链表的四个操作：
- 入栈：也就是头插法在链表中插入一个结点
- 出栈：删除链表的第一个结点
- 访问栈顶元素：访问链表的第一个结点
- 判空：判断链表的第一个结点是不是NULL
设计头文件
我们要做的第一步仍然是编写头文件。我们可以创建一个头文件"linked_stack.h"(链式栈)
#ifndef LINKED_STACK_H #define LINKED_STACK_H#include <stdbool.h> #include <stdio.h> #include <stdlib.h> typedef int ElementType;// 栈的基本单元-栈帧的结点类型定义 typedef struct node {ElementType data;struct node *next; } StackFrame;// 入栈/压栈，需要修改栈顶指针所以需要二级指针传参 void stack_push(StackFrame **top, ElementType data);// 出栈/弹栈，需要修改栈顶指针所以需要二级指针传参 ElementType stack_pop(StackFrame **top);// 访问栈顶元素, 不需要修改栈顶指针,一级指针就够了 ElementType stack_peek(const StackFrame *top);// 链式栈判空, 不需要修改栈顶指针,一级指针就够了 bool is_empty(const StackFrame *top);#endif // !LINKED_STACK_H注意事项：
- 入栈和出栈的函数需要对传入的栈顶指针做出修改，所以需要传入栈顶指针的二级指针！！
- 访问和判空则不需要修改栈帧指针，直接传入指针即可。可以使用const修饰它，这是一个好习惯。
实现判空
判空是最容易实现的，而且判空对后续操作会有影响，所以我们可以最先实现它。参考代码如下：
// 链式栈判空 bool is_empty(const StackFrame *top) {return top == NULL; }
实现入栈
所谓入栈，也就是在链表的头部，使用头插法插入一个结点。这个逻辑我们之前已经写过了，这里只需要注意二级指针的处理就可以了，参考代码如下：
// 入栈/压栈 也就是链表的头插法 void stack_push(StackFrame **top, ElementType data) {// 1.创建新的栈帧StackFrame *new_frame = malloc(sizeof(StackFrame));if (new_frame == NULL) {printf("malloc failed in stack_push.\n");exit(1);}// 2.初始化这个新栈帧new_frame->data = data;new_frame->next = *top;// 3.更新栈顶指针*top = new_frame; }注意二级指针解引用一次可以用于修改原本实参的一级指针。
实现出栈
所谓出栈，也就是根据头指针删除链表的第一个结点。这个逻辑我们也很熟悉了，参考代码如下：
// 出栈/弹栈，也就是在链表头部删除一个结点 ElementType stack_pop(StackFrame **top) {// 1.对栈判空,如果栈顶有元素,才进行出栈操作if (is_empty(*top)) {// 栈为空printf("error: stack is empty.\n");exit(-1);}// 2.先用一个临时指针保存栈顶元素的next栈帧StackFrame *tmp = *top;// 3.更新栈顶指针*top = tmp->next;// 4.将栈顶元素保存以作为返回值ElementType ret = tmp->data;// 4.free栈顶元素free(tmp);return ret; }注意，要先判空再执行出栈操作，否则会因解引用空指针导致错误。
实现访问栈顶元素
// 访问栈顶元素 ElementType stack_peek(const StackFrame *top) {// 对栈判空,如果栈顶有元素,才进行出栈操作if (is_empty(top)) {// 栈为空,没有栈顶元素可以访问printf("error: stack is empty.\n");exit(-1);}return top->data; }仍然要注意先判空，才能解引用。
补充: 不使用二级指针的链式栈
#ifndef LINKED_STACK_H #define LINKED_STACK_H #include <stdbool.h> #include <stdio.h> #include <stdlib.h>typedef int ElementType;// 栈的一个结点栈帧,类型定义 typedef struct node_s {ElementType data;struct node_s *next; }StackFrame; typedef struct {StackFrame *top; // 栈顶指针 }LinkedStack;// 基本操作 // 创建链式栈 LinkedStack *stack_create(); // 销毁链式栈 void stack_destroy(LinkedStack *stack); // 判空 bool is_empty(LinkedStack *stack); // 入栈 void stack_push(LinkedStack *stack, ElementType data); // 出栈并返回栈顶元素 ElementType stack_pop(LinkedStack *stack); // 访问栈顶元素 ElementType stack_peek(LinkedStack *stack);#endif // !LINKED_STACK_H这些函数的实现可以参考以下代码：
#include "linked_stack.h"// 新建一个空栈 LinkedStack *stack_create() {// callock可以不用手动初始化空指针return calloc(1, sizeof(LinkedStack)); } // 对于链式栈而言，销毁栈就是销毁链表 void stack_destroy(LinkedStack *stack) {// 相当于遍历链表(出栈)然后在遍历中逐个free结点StackFrame *curr = stack->top;while (curr != NULL) {StackFrame *tmp = curr->next; // 保存后继结点free(curr);curr = tmp;}// 最后free栈结构体free(stack); }bool is_empty(LinkedStack *stack) {return stack->top == NULL; }// 相当于链表头插法插入结点，栈顶指针相当于链表的头指针 void stack_push(LinkedStack *stack, ElementType data) {// 1.新建一个栈帧结点StackFrame *new_frame = malloc(sizeof(StackFrame));if (new_frame == NULL) {printf("malloc failed in stack_push.\n");exit(1);}// 2.初始化新栈帧new_frame->data = data;new_frame->next = stack->top;// 3.更新栈顶指针stack->top = new_frame; }// 相当于链表在头部删除第一个结点,栈顶指针相当于链表的头指针 ElementType stack_pop(LinkedStack *stack) {// 1.栈判空处理if (is_empty(stack)) {printf("error: stack is empty.\n");exit(1);}// 2.出栈返回栈顶元素,并free结点,更新栈顶指针StackFrame *curr = stack->top;ElementType data = curr->data;stack->top = curr->next;free(curr);return data; } ElementType stack_peek(LinkedStack *stack) {if (is_empty(stack)) {printf("error: stack is empty.\n");exit(1);}return stack->top->data; }
补充: 动态数组栈
基于动态数组，我们也完全可以实现一个可以自动扩容的动态数组栈。首先基于以下头文件：
#ifndef DYNAMIC_STACK_H #define DYNAMIC_STACK_H #include <stdio.h> #include <stdlib.h> #include <stdbool.h>typedef int ElementType;typedef struct {ElementType *elements; // 指向动态数组首元素的指针int size; // 元素的个数int capacity; // 数组的容量，也就是栈的容量 } DynamicStack;// 创建动态数组栈 DynamicStack *stack_create(); // 销毁动态数组栈 void stack_destroy(DynamicStack *s); // 入栈 void stack_push(DynamicStack *s, ElementType val); // 出栈并返回栈顶元素 ElementType stack_pop(DynamicStack *s); // 访问栈顶元素 ElementType stack_peek(DynamicStack *s); // 判空 bool is_empty(DynamicStack *s);#endif // !DYNAMIC_ARR_STACK_H这些函数的实现可以参考以下代码：
#include "dynamic_stack.h" #define DEFAULT_CAPACITY 8 // 动态栈的默认容量 #define THRESHOLD 1024 // 扩容阈值// 实现扩容机制 static void grow_capacity(DynamicStack *s) {// 扩容策略: 超过阈值则1.5倍的扩容，否则2倍的扩容int new_capacity = (s->capacity >= THRESHOLD) ?(s->capacity + (s->capacity >> 1)) :(s->capacity << 1);// 使用realloc函数实现扩容，重新分配内存ElementType *new_arr = realloc(s->elements, new_capacity * sizeof(ElementType));if (new_arr == NULL) {printf("Error: realloc failed in grow_capacity\n");exit(1);}// 更新动态数组栈结构体的信息s->elements = new_arr;s->capacity = new_capacity; } // 创建一个动态数组栈 DynamicStack *stack_create() {DynamicStack *s = malloc(sizeof(DynamicStack));if (s == NULL) {printf("malloc failed in stack_create.\n");return NULL;}// 初始化动态数组 s->size = 0;s->capacity = DEFAULT_CAPACITY;s->elements = malloc(DEFAULT_CAPACITY * sizeof(ElementType));if (s->elements == NULL) {free(s);printf("malloc failed in stack_create.\n");return NULL;}return s; } // 销毁一个栈 void stack_destroy(DynamicStack *s) {// 先释放动态数组free(s->elements);// 再释放栈结构体free(s); }// 将数组末尾视为栈顶，将size属性作为新插入结点的下标，这就是入栈 void stack_push(DynamicStack *s, ElementType val) {if (s->capacity == s->size) {// 栈满了,需要扩容grow_capacity(s);}// 可以直接把size作为入栈出栈的操作索引s->elements[s->size] = val;s->size++;// 上面的两行代码可以合并成一行// s->elements[s->size++] = val; }// 将数组末尾视为栈顶，将size属性减1，这就是出栈。元素取值并不用改变 ElementType stack_pop(DynamicStack *s) {if (is_empty(s)) {printf("Error: stack is empty\n");exit(1);}s->size--;return s->elements[s->size];// 上面的两行代码可以合并成一行// return s->elements[--(s->size)]; } // 访问栈顶元素 ElementType stack_peek(DynamicStack *s) {if (is_empty(s)) {printf("Error: stack is empty\n");exit(1);}return s->elements[s->size - 1]; } // 判空 bool is_empty(DynamicStack *s) {return s->size == 0; }
栈的应用场景
栈特别适用那些存在"后进先出"逻辑的场景，在实际的开发，栈很常用。栈至少可以应用于以下领域：
- 函数调用机制
- 括号匹配问题
- 表达式求值问题
- 浏览器历史记录前进后退功能
- 深度优先遍历算法（一般直接用函数调用者递归实现）
括号匹配问题
栈的核心操作是入栈和出栈，这和括号匹配有啥关系呢？
很简单按照下列思路就可以了：
- 遍历整个字符串
- 遇到任意左括号，就将它的对应右括号入栈
遇到任意右括号：
- 先判断当前栈是否为空，如果栈为空说明括号匹配失败
在栈不为空的前提下，立刻将当前栈顶元素出栈，判断栈顶元素是否和该右括号是同类型右括号
- 如果不是，说明括号匹配失败
- 如果是同类型右括号，那就继续遍历字符串重复上面的操作。
- 如果遍历完字符串，发现栈也同时为空，说明匹配括号成功。如果发现栈中还有残留的右括号，那么说明匹配失败。
我们使用上面已经实现的一个链式栈来辅助完成，参考的代码实现如下：
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <stdbool.h> #include "linked_stack.h" // 已实现的链式栈char get_right_bracket(char ch) {switch (ch) {case '{': return '}';case '[': return ']';case '(': return ')';default: return 0;} } bool is_left_bracket(char ch) {return ch == '{'|| ch == '['|| ch == '('; }bool is_right_bracket(char ch) {return ch == '}'|| ch == ']'|| ch == ')'; }bool is_matching(char *str, LinkedStack *stack) {while (*str) {// 排除非括号字符if (is_left_bracket(*str)) {// 字符是左括号,于是将它对应的右括号入栈char right_bracket = get_right_bracket(*str);stack_push(stack, right_bracket);}if (is_right_bracket(*str)) {// 如果遇到右括号时栈为空,说明右括号在前面,匹配失败// 如果栈不为空就出栈,和当前字符比较,如果不一致就匹配失败if (is_empty(stack) || stack_pop(stack) != *str) {return false;}}str++;}// 字符串遍历完成,判断栈是否空return is_empty(stack); }int main(void) {LinkedStack *stack = stack_create();char *str = "1()23{[}";if (is_matching(str, stack)) {printf("匹配成功!\n");}else {printf("匹配失败!\n");}stack_destroy(stack);return 0; }若传入的字符串不包含括号，此函数也会返回true，没有括号那也算是匹配成功吧。
表达式求值
表达式求值对于任何编程语言而言都是基础逻辑，这个过程一般发生在程序的运行期间。
程序员在代码中输入的表达式，一般被我们称之为"中缀表达式"，也就是我们日常生活、数学中使用的表达式，指的是将运算符放在操作数中间的一种表达式，如：
A + B7 * 3(1 + 2) * (3 - 4)- ..
中缀表达式的主要特点是它们对于人类来说非常直观，但如果让计算机直接处理中缀表达式的求值，就意味着需要像人类一样考虑优先级和括号等问题，实现起来就太麻烦了，一般计算机都不会直接处理中缀表达式。
为了能够在计算机中更轻松的处理表达式求值，普遍会先把中缀表达式处理成"后缀表达式"，也就是一种将运算符放在操作数后面的表达式形式，如：
A B +等价于A + B7 3 *等价于7 * 31 2 + 3 4 - *等价于(1 + 2) * (3 - 4)- ...
后缀表达式虽然对于人类来说不是特别直观比较容易摸不到头脑，但对于计算机而言，进行一些特殊处理，可以很容易很轻松地进行表达式求值运算。
总之，在计算机内部处理表达式求值问题时，往往会存在两个过程：
- 将中缀表达式处理成后缀表达式
- 利用后缀表达式计算求值
而这两个过程，大多都会选择使用栈来辅助完成，利用栈的"后进先出"的特点。
转换成后缀表达式
中缀表达式转换成后缀表达式的过程，需要一个运算符栈来辅助完成，大致过程思路如下：
- 从左往右遍历中缀表达式：
- 如果遇到操作数：直接将其添加到结果后缀表达式中，不进栈。
如果遇到操作符（如
+,-,*,/），那么就比较当前遍历到的运算符与运算符栈顶的运算符的优先级：
- 如果当前运算符的优先级高于栈顶运算符的优先级，或者栈为空，则将当前运算符压入栈中。
- 如果当前运算符的优先级低于或等于栈顶运算符的优先级，则需要将栈顶的运算符弹栈并添加到后缀表达式中，然后再次比较新的栈顶运算符与当前操作符的优先级。这一过程持续进行，直到当前运算符可以被压入栈中。
- 如果当前栈顶是一个左括号，那么不论是什么运算符，都直接将运算符入栈。
- 如果遇到左括号
(：立刻将它压入运算符栈。- 如果遇到右括号
)：立刻将运算符栈中的运算符弹栈并输出到后缀表达式中，这个过程会持续到遇到左括号为止。但不会将左括号添加到后缀表达式中，只是从运算符栈中移除它。且也不会把右括号添加到后缀表达式中，后缀表达式中不存在小括号。- 遍历完中缀表达式后，若运算符栈中还剩余运算符，则将这些运算符依次弹栈，添加到后缀表达式中。
- 得到最终的后缀表达式结果。
举个例子，将中缀表达式
2 * (3 + 4) / 2 - 2转换为后缀表达式：
- 扫描到
2，它是操作数，所以添加到结果后缀表达式：2- 扫描到
*，此时栈为空，压入运算符栈：栈内为*(左边表示栈顶)- 扫描到
(，遇到左小括号立刻压入操作符栈：栈内为( *- 扫描到
3，它是操作数，添加到后缀表达式：2 3- 扫描到
+，当前栈顶是左小括号，直接将加号压入运算符栈：栈内为+ ( *- 扫描到
4，添加到后缀表达式：2 3 4- 扫描到
)，弹出栈内操作符直到遇到(：后缀表达式变为2 3 4 +，栈内为*- 扫描到
/，由于其优先级与栈顶的*相同，根据左结合性，弹出*并加入后缀表达式，然后将/压入栈：后缀表达式为2 3 4 + *，栈内为/- 扫描到
2，添加到后缀表达式：2 3 4 + * 2- 扫描到
-，它的优先级不如栈顶的/，于是将/出栈加入后缀表达式中，并让-入栈。此时后缀表达式是2 3 4 + * 2 /，栈内为：-- 最后扫描到
2，它是操作数，直接添加到后缀表达式中2 3 4 + * 2 / 2。- 最后，弹出栈内剩余的操作符并添加到后缀表达式：
2 3 4 + * 2 / 2 -现在你已经得到了一个后缀表达式，那么接下来我们仍然可以利用栈来计算这个后缀表达式。
下列是利用C语言代码实现，中缀表达式转换为中缀表达式的过程。只考虑"+ - * /"四种运算符以及"()"，只考虑整数运算。
代码实现如下：
#include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <string.h>#define MAX_LEN 100 // 定义栈的最大容量// 定义操作符栈，进出栈的都是操作符字符 typedef struct {int top; // 栈顶下标char ops[MAX_LEN]; // 用于操作符进出栈的数组 } OperatorStack;// 初始化栈 void init_stack(OperatorStack *s) {s->top = -1; // 初始化栈顶索引为-1，表示栈为空 }// 检查栈是否为空 int is_empty(const OperatorStack *s) {return s->top == -1; }// 检查栈是否已满 int is_full(const OperatorStack *s) {return s->top == MAX_LEN - 1; }// 压栈操作 void push(OperatorStack *s, char op) {if (!is_full(s)) {s->top++; // 栈顶指针先上移s->ops[s->top] = op; // 将操作符压入栈顶}else {printf("error: Stack is full!\n"); // 栈满时的警告} }// 出栈操作 char pop(OperatorStack *s) {if (!is_empty(s)) {char op = s->ops[s->top]; // 获取栈顶元素s->top--; // 栈顶指针下移return op;}else {printf("error: Stack is empty!\n"); // 栈空时的警告return '\0'; // 返回空字符作为错误提示} }// 查看栈顶元素但不移除 char peek(const OperatorStack *s) {if (!is_empty(s)) {return s->ops[s->top]; // 返回栈顶元素}else {return '\0'; // 栈空时返回空字符} }// 判断字符是否为运算符 int is_operator(char ch) {return ch == '+' || ch == '-' || ch == '*' || ch == '/'; }// 运算符优先级判断 int precedence(char op) {switch (op) {case '+':case '-':return 1; // 低优先级case '*':case '/':return 2; // 高优先级default:return 0;} }// 中缀表达式转后缀表达式 void infix_to_postfix(const char *infix, char *postfix) {OperatorStack s;init_stack(&s);int i = 0, j = 0;char ch;while ((ch = infix[i++]) != '\0') {if (isdigit(ch)) { // 如果是数字，直接添加到后缀表达式postfix[j++] = ch;}else if (ch == '(') {push(&s, ch); // 左括号压栈}else if (ch == ')') {// 遇到右括号，弹出元素直到左括号while (!is_empty(&s) && peek(&s) != '(') {postfix[j++] = pop(&s);}pop(&s); // 弹出左括号，不加入到后缀表达式}else if (is_operator(ch)) {// 遇到运算符，弹出所有优先级高于或等于当前运算符的栈顶元素while (!is_empty(&s) && precedence(ch) <= precedence(peek(&s))) {postfix[j++] = pop(&s);}push(&s, ch); // 压入当前运算符}}// 将栈中剩余的运算符加入到后缀表达式while (!is_empty(&s)) {postfix[j++] = pop(&s);}postfix[j] = '\0'; // 结尾添加字符串终止符 }// 主函数 int main() {char infix[] = "2 * (3 + 4) / 2 - 2";char postfix[MAX_LEN];infix_to_postfix(infix, postfix);printf("中缀表达式是: %s\n", infix); // 输出中缀表达式printf("对应后缀表达式是: %s\n", postfix); // 输出后缀表达式return 0; }
后缀表达式求值
后缀表达式求值也需要利用栈结构来辅助完成，这个过程会更简单一些：
- 从左往右遍历中缀表达式：
- 如果遇到操作数：直接将其压入栈中。
如果遇到运算符：
- 从栈中弹出所需数量的操作数，执行相应的运算，然后将结果压回栈中。比如对于二元操作符（如
+,-,*,/），需要弹出两个操作数。- 注意：对于
-或/这样在意操作数前后的二元运算符来说，假如此时栈中的两个操作数是a b(左边表示栈顶)，那么它们运算规则应该是b - a。（思考一下这是为什么？）- 重复此过程，直到整个表达式被扫描完毕。
- 表达式的结果就是栈顶数值。
比如我们上面已经得到的一个后缀表达式
2 3 4 + * 2 / 2 -，利用栈，其计算过程和结果是：
- 前三个扫描到的都是操作数，于是都直接入栈。栈中元素是：
4 3 2(左边表示栈顶)- 扫描到
+，于是将栈顶的两个操作数出栈(因为加法是二元运算符)，于是计算3 + 4结果是7，将7存入栈顶。栈中元素目前是：7 2- 继续扫描到
*，于是将栈顶的两个操作数出栈(因为乘法是二元运算符)，于是计算2 * 7结果是14，将14存入栈顶。栈中元素目前是：14- 继续扫描到
2，它是一个操作数，于是直接入栈。栈中元素目前是：2 14- 继续扫描到
/，于是将栈顶的两个操作数出栈(因为除法是二元运算符)，于是计算14 / 2结果是7，将它入栈。此时栈中元素是：7- 继续扫描到
2，它是一个操作数，于是直接入栈。栈中元素目前是：2 7- 继续扫描到
-，于是将栈顶的两个操作数出栈(因为减法是二元运算符)，于是计算7 - 2结果是5，将它入栈。此时栈中元素是：5- 发现后缀表达式扫描完成，于是此时的栈顶元素
5，就是表达式的最终结果。同样基于一个操作数栈，可以实现后缀表达式求值，只考虑"+ - * /"四种运算符以及"()"，只考虑整数运算。参考代码如下：
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <ctype.h> // 用于isdigit函数#define MAX_LEN 100 // 定义栈的最大容量// 定义操作数栈,进出栈的都是后缀表达式的操作数 typedef struct {int top; // 栈顶索引int values[MAX_LEN]; // 操作数进出栈的数组 } ValueStack;// 初始化操作数栈 void init_stack(ValueStack *s) {s->top = -1; }// 检查栈是否为空 int is_empty(const ValueStack *s) {return s->top == -1; }// 检查栈是否已满 int is_full(const ValueStack *s) {return s->top == MAX_LEN - 1; }// 压栈操作 void push_value(ValueStack *s, int value) {if (!is_full(s)) {s->top += 1; // 先增加栈顶索引s->values[s->top] = value; // 将整数值压入栈顶}else {printf("error: value stack is full!\n");} }// 出栈操作 int pop_value(ValueStack *s) {if (!is_empty(s)) {int value = s->values[s->top]; // 获取栈顶元素s->top -= 1; // 栈顶索引减少return value;}else {printf("error: value stack is empty, cannot pop!\n"); // 栈空时输出错误信息return 0; // 返回0作为错误情况的默认值} }// 查看栈顶元素但不移除 int peek_value(ValueStack *s) {if (!is_empty(s)) {return s->values[s->top]; // 返回栈顶元素}else {printf("error: value stack is empty, cannot peek!\n");return 0; // 栈为空时的错误处理，返回0} }// 执行运算 int evaluate(int val1, int val2, char operator) {switch (operator) {case '+': return val1 + val2;case '-': return val1 - val2;case '*': return val1 * val2;case '/': return val1 / val2;default: return 0; // 对于非法运算符返回0} }// 后缀表达式求值 int evaluate_postfix(const char *postfix) {ValueStack s; // 声明一个操作数栈init_stack(&s); // 初始化栈，确保开始时栈是空的int i = 0; // 字符串遍历索引char ch; // 用于存储当前遍历到的字符// 遍历后缀表达式字符串直到遇到字符串结束符 '\0'while ((ch = postfix[i]) != '\0') {if (isdigit(ch)) {// 如果当前字符是数字，则将其转换为整数并压入栈中// '0'的ASCII码值用于从字符转换到相应的整数值push_value(&s, ch - '0');}else if (ch == ' ' || ch == '\t') {// 如果遇到空格或制表符，则跳过，继续遍历// 这些字符在后缀表达式中用于分隔数字和运算符}else {// 如果当前字符是运算符，则需要从栈中弹出两个操作数进行计算int val2 = pop_value(&s); // 弹出第一个操作数（右操作数）int val1 = pop_value(&s); // 弹出第二个操作数（左操作数）int result = evaluate(val1, val2, ch); // 根据运算符计算结果push_value(&s, result); // 将计算结果压回栈中}i++; // 移动索引到下一个字符}// 循环结束后，栈顶元素是整个后缀表达式的计算结果return pop_value(&s); // 弹出并返回最终结果 }// 主函数，用于测试 int main() {char postfix_exp[] = "2 3 4 + * 2 / 2 -";int result = evaluate_postfix(postfix_exp);printf("待计算的后缀表达式是 '%s' ，计算的结果是: %d\n", postfix_exp, result);return 0; }
浏览器历史前进后退功能
浏览器历史的前进后退功能，看起来很强大的功能，实际上只需要两个栈就可以实现了：
- 一个前进栈，用于存储用户在点击后退按钮后，再点击前进按钮可能访问的页面。最初是空的。
- 一个后退栈，用于指示存储用户当前访问的页面，以及用户的历史访问页面记录以用作实现后退按钮。
具体来说是：
- 访问新页面：当用户访问一个新页面时，将新访问的当前页面压入后退栈中，并立刻清空前进栈。后退栈的栈顶始终表示当前正在访问的页面。
- 后退按钮：当用户点击浏览器的后退按钮时，后退栈弹栈，并且将弹出的页面压入前进栈。后退栈弹栈后，后退栈栈顶下的一个页面就成为了新的当前页面。
- 前进按钮：前进按钮仅在前进栈不为空时生效。当用户点击浏览器的前进按钮时，前进栈弹栈，并且将弹出的页面压入后退栈。此时前进栈弹出的页面就成为了后退栈的栈顶，也就成为了新的当前页面。
这种使用两个栈的方法非常适合处理线性的浏览历史，因为它自然地模拟了后退和前进操作的LIFO（后进先出）特性。此外，它也使得浏览器能够快速访问历史记录，无需遍历整个历史列表。
栈在浏览器前进后退功能的应用，充分体现了栈可以用于记录"轨迹"的作用，在算法思想中有一种叫做"回溯"的思想，它就是利用了栈的这个特点。