栈和队列的应用

一、括号匹配

算法思想：遇到左括号入栈，遇到右括号出栈匹配。

bool BracketMatch(char *str) {
    SqStack S; InitStack(&S);
    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{')
            Push(&S, str[i]);
        else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
            if (StackEmpty(S)) return false;
            char top; Pop(&S, &top);
            if (str[i] == ')' && top != '(') return false;
            if (str[i] == ']' && top != '[') return false;
            if (str[i] == '}' && top != '{') return false;
        }
    }
    return StackEmpty(S);  // 栈空则匹配成功
}

时间复杂度 O(n)，空间复杂度 O(n)。

二、表达式求值

1. 中缀转后缀（逆波兰表达式）

• 操作数：直接输出
• 左括号：入栈
• 右括号：出栈直到遇到左括号
• 运算符：出栈优先级 $\ge$ 当前的运算符，再将当前运算符入栈

示例 a + b * c + (d * e + f) * g → 后缀 a b c * + d e * f + g * +。

2. 后缀表达式求值

操作数入栈；遇运算符弹出两个操作数计算后入栈。例 a b c * +（$a=1,b=2,c=3$）：$2*3=6\to1+6=7$。

3. 中缀表达式求值（两个栈）

操作数栈 + 运算符栈，按优先级出入栈。

三、递归

递归调用时，系统用函数调用栈保存返回地址、参数、局部变量。可转为显式栈（如斐波那契非递归）。

int Fib(int n) {            // 递归
    if (n == 0 || n == 1) return n;
    return Fib(n-1) + Fib(n-2);
}
int Fib(int n) {            // 非递归（迭代）
    if (n == 0 || n == 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; i++) { c = a + b; a = b; b = c; }
    return c;
}

四、队列的应用

1. 层次遍历（二叉树）

void LevelOrder(BiTree T) {
    Queue Q; InitQueue(&Q); EnQueue(&Q, T);
    while (!QueueEmpty(Q)) {
        BiTNode *p; DeQueue(&Q, &p); visit(p);
        if (p->lchild) EnQueue(&Q, p->lchild);
        if (p->rchild) EnQueue(&Q, p->rchild);
    }
}

2. BFS（广度优先搜索）

void BFS(Graph G, int v) {
    visit(v); visited[v] = true; EnQueue(&Q, v);
    while (!QueueEmpty(Q)) {
        DeQueue(&Q, &v);
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
            if (!visited[w]) { visit(w); visited[w] = true; EnQueue(&Q, w); }
    }
}

3. 操作系统中的应用

• FCFS 调度（先来先服务）
• 打印任务队列
• 消息队列