[数据结构] 04 - 2 - 栈的应用
这一节是【04 - 栈和队列】的第 4.1.5 小节的内容,因为篇幅较长所以单开一篇文章。
4.1.5 - 栈的应用
一、反转一个字符串
我们要用栈的方法反转 C 风格的字符串,在 C 中字符串以 \0 结尾。
(一)思路
我们只需要把原本字符串中的字符从头到尾存入一个栈中,然后再通过 popup() 依次取出字母,从头到尾修改这个字符串的字符,就完成了字符串的反转。
(二)实现
以 C 语言为例:
// 使用栈反转字符串(原地修改)
void reverseString(char *str) {
int len = strlen(str);
if (len == 0) return; // 空字符串无需处理
// 创建一个栈并初始化
Stack s;
initStack(&s);
// 将字符串所有字符依次压入栈
for (int i = 0; i < len; i++) {
push(&s, str[i]);
}
// 从栈中弹出字符,覆盖原字符串,实现反转
for (int i = 0; i < len; i++) {
str[i] = pop(&s);
}
}(三)复杂度分析
设待反转的字符串长度为 n,即 strlen(str) 的值。在 reverseString 函数中,执行了压栈和出栈两个独立的循环。
① 第一个循环:压栈
for (int i = 0; i < len; i++) {
push(&s, str[i]);
}- 遍历字符串的每个字符,进行 n 次迭代;
- 每次调用 push 函数,其中包含一次赋值操作和栈顶索引自增,均为 O(1) 操作;
- 该循环的总时间复杂度为 O(n)。
② 第二个循环:弹栈并写回
for (int i = 0; i < len; i++) {
str[i] = pop(&s);
}- 同样遍历 n 个字符,共执行 n 次迭代;
- 每次调用
pop()函数,其中仅包含一次取值和栈顶索引自减,均为 O(1) 操作; - 该循环的总时间复杂度为 O(n)。
③ 总时间复杂度
strlen()函数本身也需要遍历一次字符串以计算长度,时间复杂度为 O(n),但通常忽略不计或视为常数预处理。若严格计入,总时间复杂度仍为 O(n)。
该反转算法的时间复杂度为 O(n),其中 n 为字符串长度,对于长度为 n 的字符串,算法执行约 2n 次基本操作,常数因子小,性能良好。
④ 空间复杂度
- 栈使用固定大小数组
data[MAX_STACK],但实际压入的字符数为 n,因此使用的栈空间为 O(n); - 若
MAX_STACK视为常量(静态分配),则严格空间复杂度为 O(1)(因为数组大小固定),但通常我们认为算法需要额外存储 n 个字符,即空间复杂度为 O(n);
二、反转一个链表
(一)思路 / 回顾递归法
链表的内存不连续,无法用双指针的方法进行反转
上一章,已经讲过用迭代法和递归法反转一个链表,但那只能称为【隐式地利用了栈的特性】,并没有实际创建一个栈
参考本章【3.4 – 反转 / 反向打印链表】
https://salmon-isle.com/archives/2447
这一次,我们需要一个临时指针变量 temp 遍历整个链表,并把每个节点按顺序压入栈中。然后从栈顶开始依次弹出节点,修改 next 指针,实现逆向链接,最后修改 head 的值。
将节点按顺序压入栈后,在取出时顺序自然就是反向的
(二)实现
核心函数(C 语言):
// 使用栈反转链表(返回新头节点)
ListNode* reverseListUsingStack(ListNode* head) {
if (!head) return NULL; // 空链表直接返回
// 第一遍遍历:计算节点个数
int count = 0;
ListNode* cur = head;
while (cur) {
count++;
cur = cur->next;
}
// 分配栈空间
ListNode** stack = (ListNode**)malloc(count * sizeof(ListNode*));
if (!stack) {
fprintf(stderr, "栈内存分配失败\n");
exit(EXIT_FAILURE);
}
// 第二遍遍历:将所有节点指针压入栈
cur = head;
for (int i = 0; i < count; i++) {
stack[i] = cur;
cur = cur->next;
}
// 弹出栈并重新链接(从栈顶到栈底)
// 原链表的尾节点成为新头
ListNode* newHead = stack[count - 1];
cur = newHead;
for (int i = count - 2; i >= 0; i--) {
cur->next = stack[i];
cur = cur->next;
}
cur->next = NULL; // 新链表的尾节点(原头节点)指向NULL
free(stack); // 释放栈空间
return newHead;
}分配栈空间(一个指针数组,存储链表的节点指针):
// 分配栈空间
ListNode** stack = (ListNode**)malloc(count * sizeof(ListNode*));
if (!stack) {
fprintf(stderr, "栈内存分配失败\n");
exit(EXIT_FAILURE);
}- 使用动态数组模拟栈:动态数组元素的类型为
ListNode*(节点指针)。使用 malloc 从堆上分配count个指针的连续空间。此时 stack 就是这个连续空间的首地址;
为什么用 malloc 数组而不是链表来当栈?
- 因为长度已知;
- 只做一次性临时存储;
- 用
malloc一次分配指针数组,比链式栈少 n 次malloc/free; - 少一个
next指针域,缓存更友好; - 代码也更短。
(三)复杂度分析
显然时间复杂度为 O(n),空间复杂度也是 O(n)。
三、检查括号匹配性
(一)思路
问题描述:用栈检查三种括号 () {} [] 的匹配性,例如:
{[()]} -> 匹配
{[(])} -> 不匹配,嵌套
((())) -> 匹配
(() -> 不匹配,缺右括号核心思路:遇到左括号就入栈,遇到右括号就检查栈顶的左括号是否和它匹配。
括号有一个非常明显的特点:最晚出现的左括号,应该最先被右侧括号匹配。 这正是栈的后进先出(LIFO)。
例如 { 2 * (3 + 4) / [ 5 * (6 - 7) ] % 8 } :
- 首先遇到
{ (,均为左括号,依次入栈; - 遇到第一个右括号
),此时取出栈顶,发现其与栈顶的左括号(匹配,令(出栈; - 再往前,又连续遇到两个左括号
[ (,依次入栈。此时的栈,从栈顶到栈底依次是( [ {; - 后续又遇到
) ] },依次取出栈顶 + 匹配 + 弹出; - 最后,检查发现栈为空,并且没有未匹配的右括号,因此整个字符串的括号是匹配的。最后必须检查栈是否为空,可能剩余左括号没有对应的右括号。
(二)实现
核心函数(C 语言):
// 判断左右括号是否匹配
int isMatching(char left, char right) {
if (left == '(' && right == ')')
return 1;
if (left == '[' && right == ']')
return 1;
if (left == '{' && right == '}')
return 1;
return 0;
}
int checkBrackets(char str[]) {
// 创建并初始化一个栈
Stack s;
initStack(&s);
for (int i = 0; str[i] != '\0'; i++) {
char ch = str[i];
// 仅将三种括号字符入栈
if (ch == '(' || ch == '[' || ch == '{') {
push(&s, ch);
}
else if (ch == ')' || ch == ']' || ch == '}') {
// 如果栈为空时出现右括号,一定不匹配
if (isEmpty(&s)) {
return 0;
}
// 无论是否匹配,都先将栈顶取出
char left = pop(&s);
if (!isMatching(left, ch)) {
return 0;
}
}
}
// 最后,如果栈为空,则括号完全匹配;
// 若栈不为空,说明有左括号未找到右括号,不匹配;
return isEmpty(&s);
}四、前缀, 中缀和后缀
(一)算数表达式的三种写法
前缀、中缀和后缀指的是算数表达式的三种写法,它们的共通结构就是由两个操作数(operands)和一个操作符(operator)组成,与栈关系密切:
| 类型 | 表达式 | 特点 |
|---|---|---|
| 前缀 Prefix | a + b * c - d / e | 运算符在操作数前 |
| 中缀 Infix | - + a * b c / d e | 运算符在操作数中间 |
| 后缀 Postfix | a b c * + d e / - | 运算符在操作数后 |
1. 中缀表达式(Infix)
中缀表达式(Infix expression)是人类惯用的形式,但是中缀表达式存在运算优先级。
计算机计算中缀表达式,必须考虑:
- 括号;
- 运算符的优先级;
- 运算符的结合性。
2. 后缀表达式(Postfix)
后缀表达式又叫逆波兰表达式(Reverse Polish Notation),在 20 世纪 50 年代被波兰逻辑学家 Jan Lukasiewicz 提出。
后缀表达式不需要额外考虑运算顺序,并且非常适合用栈处理。
手算一个后缀表达式的例子
例如,现在要用栈计算 (2+3)×4:
- 其后缀表达式是
2 3 + 4 *; - 栈初始为空,遇到 2 时 push(2),遇到 3 时 push(3);
- 遇到二元运算符加号,它需要两个操作数,所以从栈中弹出两个数(2 和 3)并进行加法计算,得到 5,并 push(5);
- 遇到 4 时 push(4);
- 遇到二元运算符乘号,它需要两个操作数,所以从栈中弹出两个数(4 和 5)并进行乘法计算,得到 20,并 push(20);
- 没有更多的操作数,此时栈中唯一的数就是计算结果。
3. 前缀表达式(Prefix)
前缀表达式又叫波兰表达式(Polish Notation),前缀表达式同样不需要考虑运算顺序,可以用栈处理。
与后缀表达式不同的是,表达式 的前缀表达式是 + 2 * 3 4,在求前缀表达式的值的时候需要从右向左进行扫描。
(二)中缀表达式转后缀
1. 思路
中缀转后缀需要一个运算符栈和一个输出变量,基本思想是:
- 操作数直接输出,运算符存入栈中;
- 根据优先级决定什么时候弹出运算符;
- 遇到左括号直接压栈,遇到右括号不断弹出栈顶运算符,直到遇到左括号。
2. 实例
【例子 1】将 A + B * C 转为 A B C * +
(1)将 A + B * C 转为 A B C * +:
- 遇操作数 A,直接输出;
- 遇加法运算符,直接
push('+'); - 遇操作数 B,直接输出,此时输出:A B;
- 遇乘法运算符,因为乘法的优先级高于加法,所以
push('*'); - 遇操作数 C,直接输出,此时输出:A B C;
- 扫描结束,依次将栈中的运算符弹出并输出,最后输出:
A B C * +;
【例子 2】将 (A + B) * C 转为 A B + C *
(2)将 (A + B) * C 转为 A B + C *:
- 遇左括号,
push('('); - 遇操作数 A,直接输出;
- 遇加法运算符,直接
push('+'); - 遇操作数 B,直接输出,此时输出:A B;
- 遇右括号,不断弹出栈顶运算符直到遇到左括号,所以输出:A B +;
- 遇乘法运算符,直接
push('*'); - 遇操作数 C,直接输出,此时输出:A B + C;
- 扫描结束,依次将栈中的运算符弹出并输出,最后输出:
A B + C *;
3. 实现
这份代码的核心是:
- 左括号直接入栈;
- 右括号一直出栈到左括号;
- 遇到运算符时,把栈中优先级不低于自己的运算符先弹出,然后自己入栈。
第三条即当前运算符来了以后,要先看看栈顶有没有“比我更应该先算”的运算符。如果有,就先把栈顶的运算符弹出去;如果没有,当前运算符就入栈。
以 C 语言为例:
#include <stdio.h>
#include <ctype.h>
#define MAX 100
char stack[MAX];
int top = -1;
// 入栈
void push(char ch) {
stack[++top] = ch;
}
// 出栈
char pop() {
return stack[top--];
}
// 查看栈顶元素
char peek() {
return stack[top];
}
// 判断运算符优先级
int priority(char ch) {
if (ch == '+' || ch == '-')
return 1;
if (ch == '*' || ch == '/')
return 2;
return 0;
}
int main() {
char infix[MAX];
char postfix[MAX];
int i = 0;
int j = 0;
printf("请输入中缀表达式:");
scanf("%s", infix);
while (infix[i] != '\0') {
char ch = infix[i];
// 1. 如果是操作数,直接放入后缀表达式
if (isalnum(ch)) {
postfix[j++] = ch;
}
// 2. 如果是左括号,直接入栈
else if (ch == '(') {
push(ch);
}
// 3. 如果是右括号
else if (ch == ')') {
// 将左括号之前的运算符全部弹出
while (top != -1 && peek() != '(') {
postfix[j++] = pop();
}
// 弹出左括号,但不加入后缀表达式
pop();
}
// 4. 如果是运算符
else {
// 如果栈顶运算符优先级 >= 当前运算符
// 就先把栈顶运算符弹出
while (top != -1 &&
peek() != '(' &&
priority(peek()) >= priority(ch)) {
postfix[j++] = pop();
}
// 当前运算符入栈
push(ch);
}
i++;
}
// 5. 表达式扫描结束,把栈中剩余运算符全部弹出
while (top != -1) {
postfix[j++] = pop();
}
// 字符串结束标志
postfix[j] = '\0';
printf("后缀表达式:%s\n", postfix);
return 0;
}