【数据结构与算法】第12篇：栈（二）：链式栈与括号匹配问题

一、链式栈的实现

1.1 链式栈的结构

链式栈用链表存储数据，栈顶就是链表的头结点。因为单链表的头插和头删都是O(1)，非常适合做栈。

text

栈顶 → [data|next] → [data|next] → [data|next] → NULL

节点结构：

c

typedef struct StackNode { int data; // 数据域 struct StackNode *next; // 指针域 } StackNode, *PStackNode; typedef struct { PStackNode top; // 栈顶指针 int size; // 栈中元素个数 } LinkStack;

1.2 初始化

c

void initStack(LinkStack *stack) { stack->top = NULL; stack->size = 0; }

1.3 判断空栈

c

int isEmpty(LinkStack *stack) { return stack->top == NULL; }

1.4 入栈（push）

入栈就是在链表头部插入节点。

c

int push(LinkStack *stack, int value) { PStackNode newNode = (PStackNode)malloc(sizeof(StackNode)); if (newNode == NULL) { printf("内存分配失败\n"); return -1; } newNode->data = value; newNode->next = stack->top; stack->top = newNode; stack->size++; return 0; }

1.5 出栈（pop）

出栈就是删除链表头节点。

c

int pop(LinkStack *stack, int *value) { if (isEmpty(stack)) { printf("栈为空，无法出栈\n"); return -1; } PStackNode temp = stack->top; *value = temp->data; stack->top = temp->next; free(temp); stack->size--; return 0; }

1.6 获取栈顶元素

c

int getTop(LinkStack *stack, int *value) { if (isEmpty(stack)) { printf("栈为空\n"); return -1; } *value = stack->top->data; return 0; }

1.7 获取栈的大小

c

int getSize(LinkStack *stack) { return stack->size; }

1.8 销毁栈

c

void destroyStack(LinkStack *stack) { PStackNode cur = stack->top; while (cur != NULL) { PStackNode temp = cur; cur = cur->next; free(temp); } stack->top = NULL; stack->size = 0; }

二、链式栈完整代码

c

#include <stdio.h> #include <stdlib.h> typedef struct StackNode { int data; struct StackNode *next; } StackNode, *PStackNode; typedef struct { PStackNode top; int size; } LinkStack; void initStack(LinkStack *stack) { stack->top = NULL; stack->size = 0; } int isEmpty(LinkStack *stack) { return stack->top == NULL; } int push(LinkStack *stack, int value) { PStackNode newNode = (PStackNode)malloc(sizeof(StackNode)); if (newNode == NULL) { printf("内存分配失败\n"); return -1; } newNode->data = value; newNode->next = stack->top; stack->top = newNode; stack->size++; return 0; } int pop(LinkStack *stack, int *value) { if (isEmpty(stack)) { printf("栈为空，无法出栈\n"); return -1; } PStackNode temp = stack->top; *value = temp->data; stack->top = temp->next; free(temp); stack->size--; return 0; } int getTop(LinkStack *stack, int *value) { if (isEmpty(stack)) { printf("栈为空\n"); return -1; } *value = stack->top->data; return 0; } int getSize(LinkStack *stack) { return stack->size; } void destroyStack(LinkStack *stack) { PStackNode cur = stack->top; while (cur != NULL) { PStackNode temp = cur; cur = cur->next; free(temp); } stack->top = NULL; stack->size = 0; } void printStack(LinkStack *stack) { printf("栈顶 → "); PStackNode cur = stack->top; while (cur != NULL) { printf("[%d] ", cur->data); if (cur->next != NULL) printf("\n "); cur = cur->next; } printf("\n栈底\n"); } int main() { LinkStack stack; initStack(&stack); push(&stack, 10); push(&stack, 20); push(&stack, 30); printStack(&stack); printf("栈大小: %d\n", getSize(&stack)); int val; pop(&stack, &val); printf("出栈: %d\n", val); pop(&stack, &val); printf("出栈: %d\n", val); printStack(&stack); printf("栈大小: %d\n", getSize(&stack)); destroyStack(&stack); return 0; }

运行结果：

text

栈顶 → [30] [20] [10] 栈底 栈大小: 3 出栈: 30 出栈: 20 栈顶 → [10] 栈底 栈大小: 1

三、经典应用：括号匹配

3.1 问题描述

给定一个字符串，只包含()[]{}三种括号，判断括号是否匹配。

匹配规则：

• 左括号必须用相同类型的右括号闭合

• 左括号必须以正确的顺序闭合

• 嵌套时，内层的括号必须先闭合

示例：

• "()"→ 匹配

• "()[]{}"→ 匹配

• "{[]}"→ 匹配

• "([)]"→ 不匹配（顺序错误）

• "((()"→ 不匹配（数量不对）

3.2 算法思路

用栈来实现：

1. 遍历字符串的每个字符

2. 如果是左括号([{，则入栈

3. 如果是右括号)]}：

   • 如果栈为空，说明没有对应的左括号，返回不匹配

   • 如果栈顶元素不是对应的左括号，返回不匹配

   • 如果匹配，则栈顶元素出栈

4. 遍历结束后，如果栈为空则匹配，否则不匹配

画个图理解"{[]}"：

text

遍历 '{' : 栈 → [ { ] 遍历 '[' : 栈 → [ { [ ] 遍历 ']' : 栈顶是'['，匹配，弹出 → 栈 → [ { ] 遍历 '}' : 栈顶是'{'，匹配，弹出 → 栈 → [ ] 结束，栈为空 → 匹配成功

3.3 代码实现

c

#include <stdio.h> #include <stdlib.h> #include <string.h> // 链式栈节点（存储字符） typedef struct CharNode { char data; struct CharNode *next; } CharNode, *PCharNode; typedef struct { PCharNode top; int size; } CharStack; void initCharStack(CharStack *stack) { stack->top = NULL; stack->size = 0; } int isCharStackEmpty(CharStack *stack) { return stack->top == NULL; } int charPush(CharStack *stack, char value) { PCharNode newNode = (PCharNode)malloc(sizeof(CharNode)); if (newNode == NULL) return -1; newNode->data = value; newNode->next = stack->top; stack->top = newNode; stack->size++; return 0; } int charPop(CharStack *stack, char *value) { if (isCharStackEmpty(stack)) return -1; PCharNode temp = stack->top; *value = temp->data; stack->top = temp->next; free(temp); stack->size--; return 0; } int charGetTop(CharStack *stack, char *value) { if (isCharStackEmpty(stack)) return -1; *value = stack->top->data; return 0; } void destroyCharStack(CharStack *stack) { PCharNode cur = stack->top; while (cur != NULL) { PCharNode temp = cur; cur = cur->next; free(temp); } stack->top = NULL; stack->size = 0; } // 判断两个括号是否匹配 int isMatch(char left, char right) { return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}'); } // 括号匹配函数 int bracketMatch(const char *str) { CharStack stack; initCharStack(&stack); for (int i = 0; str[i] != '\0'; i++) {

char ch = str[i]; // 左括号入栈 if (ch == '(' || ch == '[' || ch == '{') { charPush(&stack, ch); } // 右括号处理 else if (ch == ')' || ch == ']' || ch == '}') { // 栈为空，没有匹配的左括号 if (isCharStackEmpty(&stack)) { destroyCharStack(&stack); return 0; } char topChar; charGetTop(&stack, &topChar); // 不匹配 if (!isMatch(topChar, ch)) { destroyCharStack(&stack); return 0; } // 匹配，弹出栈顶 charPop(&stack, &topChar); } // 其他字符忽略（如字母、数字） } // 栈空则完全匹配 int result = isCharStackEmpty(&stack); destroyCharStack(&stack); return result; } int main() { char test1[] = "()"; char test2[] = "()[]{}"; char test3[] = "{[()]}"; char test4[] = "([)]"; char test5[] = "((()"; char test6[] = "a+b*(c-d)/{e+f}"; printf("\"%s\" : %s\n", test1, bracketMatch(test1) ? "匹配" : "不匹配"); printf("\"%s\" : %s\n", test2, bracketMatch(test2) ? "匹配" : "不匹配"); printf("\"%s\" : %s\n", test3, bracketMatch(test3) ? "匹配" : "不匹配"); printf("\"%s\" : %s\n", test4, bracketMatch(test4) ? "匹配" : "不匹配"); printf("\"%s\" : %s\n", test5, bracketMatch(test5) ? "匹配" : "不匹配"); printf("\"%s\" : %s\n", test6, bracketMatch(test6) ? "匹配" : "不匹配"); return 0; }

运行结果：

text

"()" : 匹配 "()[]{}" : 匹配 "{[()]}" : 匹配 "([)]" : 不匹配 "((()" : 不匹配 "a+b*(c-d)/{e+f}" : 匹配

四、顺序栈 vs 链式栈

选择建议：

• 如果栈的大小可以预估，用顺序栈更简单高效

• 如果栈的大小不确定，用链式栈更安全

五、栈的其他应用

括号匹配是栈的经典应用，栈还常用于：

六、小结

这一篇我们实现了链式栈，并用它解决了括号匹配问题：

括号匹配的核心思想：

• 遇到左括号就压栈

• 遇到右括号就弹栈比较

• 栈空且遍历完才算匹配

下一篇我们会讲栈的另一个经典应用：表达式求值（中缀转后缀并计算）。

七、思考题

1. 链式栈的入栈和出栈为什么选择在头部操作？如果在尾部操作会怎样？

2. 括号匹配算法中，如果表达式中包含其他字符（如字母、数字），为什么可以直接忽略？

3. 下面这个字符串能匹配吗？为什么？"({[}])"

4. 尝试实现一个函数，判断HTML标签是否匹配（如<div><p></p></div>）。

欢迎在评论区讨论你的答案。