[数据结构] 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)。

③ 总时间复杂度

  • T(n)=O(n)+O(n)=O(n)T(n) = O(n) + O(n) = 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 } :

  1. 首先遇到 { ( ,均为左括号,依次入栈;
  2. 遇到第一个右括号 ) ,此时取出栈顶,发现其与栈顶的左括号 ( 匹配,令 ( 出栈;
  3. 再往前,又连续遇到两个左括号 [ (,依次入栈。此时的栈,从栈顶到栈底依次是 ( [ {;
  4. 后续又遇到 ) ] },依次取出栈顶 + 匹配 + 弹出;
  5. 最后,检查发现栈为空,并且没有未匹配的右括号,因此整个字符串的括号是匹配的。最后必须检查栈是否为空,可能剩余左括号没有对应的右括号。

(二)实现

核心函数(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)组成,与栈关系密切:

类型表达式特点
前缀 Prefixa + b * c - d / e运算符在操作数前
中缀 Infix- + a * b c / d e运算符在操作数中间
后缀 Postfixa b c * + d e / -运算符在操作数后

1. 中缀表达式(Infix)

中缀表达式(Infix expression)是人类惯用的形式,但是中缀表达式存在运算优先级。

计算机计算中缀表达式,必须考虑:

  • 括号;
  • 运算符的优先级;
  • 运算符的结合性。

2. 后缀表达式(Postfix)

后缀表达式又叫逆波兰表达式(Reverse Polish Notation),在 20 世纪 50 年代被波兰逻辑学家 Jan Lukasiewicz 提出。

后缀表达式不需要额外考虑运算顺序,并且非常适合用栈处理。

手算一个后缀表达式的例子

例如,现在要用栈计算 (2+3)×4:

  1. 其后缀表达式是 2 3 + 4 *;
  2. 栈初始为空,遇到 2 时 push(2),遇到 3 时 push(3);
  3. 遇到二元运算符加号,它需要两个操作数,所以从栈中弹出两个数(2 和 3)并进行加法计算,得到 5,并 push(5);
  4. 遇到 4 时 push(4);
  5. 遇到二元运算符乘号,它需要两个操作数,所以从栈中弹出两个数(4 和 5)并进行乘法计算,得到 20,并 push(20);
  6. 没有更多的操作数,此时栈中唯一的数就是计算结果。

3. 前缀表达式(Prefix)

前缀表达式又叫波兰表达式(Polish Notation),前缀表达式同样不需要考虑运算顺序,可以用栈处理。

与后缀表达式不同的是,表达式 (2+3)×4(2+3)×4 的前缀表达式是 + 2 * 3 4,在求前缀表达式的值的时候需要从右向左进行扫描。

(二)中缀表达式转后缀

1. 思路

中缀转后缀需要一个运算符栈和一个输出变量,基本思想是:

  1. 操作数直接输出,运算符存入栈中;
  2. 根据优先级决定什么时候弹出运算符;
  3. 遇到左括号直接压栈,遇到右括号不断弹出栈顶运算符,直到遇到左括号。

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;
}