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

一、链式栈的实现1.1 链式栈的结构链式栈用链表存储数据栈顶就是链表的头结点。因为单链表的头插和头删都是O(1)非常适合做栈。text栈顶 → [data|next] → [data|next] → [data|next] → NULL节点结构ctypedef struct StackNode { int data; // 数据域 struct StackNode *next; // 指针域 } StackNode, *PStackNode; typedef struct { PStackNode top; // 栈顶指针 int size; // 栈中元素个数 } LinkStack;1.2 初始化cvoid initStack(LinkStack *stack) { stack-top NULL; stack-size 0; }1.3 判断空栈cint isEmpty(LinkStack *stack) { return stack-top NULL; }1.4 入栈push入栈就是在链表头部插入节点。cint 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出栈就是删除链表头节点。cint 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 获取栈顶元素cint getTop(LinkStack *stack, int *value) { if (isEmpty(stack)) { printf(栈为空\n); return -1; } *value stack-top-data; return 0; }1.7 获取栈的大小cint getSize(LinkStack *stack) { return stack-size; }1.8 销毁栈cvoid 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 算法思路用栈来实现遍历字符串的每个字符如果是左括号([{则入栈如果是右括号)]}如果栈为空说明没有对应的左括号返回不匹配如果栈顶元素不是对应的左括号返回不匹配如果匹配则栈顶元素出栈遍历结束后如果栈为空则匹配否则不匹配画个图理解{[]}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[] ab*(c-d)/{ef}; 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() : 匹配 ()[]{} : 匹配 {[()]} : 匹配 ([)] : 不匹配 ((() : 不匹配 ab*(c-d)/{ef} : 匹配四、顺序栈 vs 链式栈对比项顺序栈链式栈存储方式数组连续内存链表非连续容量固定可能溢出动态受内存限制入栈O(1)O(1)出栈O(1)O(1)内存利用率可能浪费每节点多一个指针适用场景大小已知大小未知动态变化选择建议如果栈的大小可以预估用顺序栈更简单高效如果栈的大小不确定用链式栈更安全五、栈的其他应用括号匹配是栈的经典应用栈还常用于应用说明表达式求值中缀转后缀计算表达式函数调用栈递归函数的底层实现撤销操作CtrlZ 撤销浏览器后退记录浏览历史深度优先搜索图的DFS算法六、小结这一篇我们实现了链式栈并用它解决了括号匹配问题内容要点链式栈用单链表实现头插头删没有容量限制入栈O(1)在链表头部插入出栈O(1)删除链表头部括号匹配左括号入栈右括号与栈顶匹配时间复杂度O(n)遍历一次字符串括号匹配的核心思想遇到左括号就压栈遇到右括号就弹栈比较栈空且遍历完才算匹配下一篇我们会讲栈的另一个经典应用表达式求值中缀转后缀并计算。七、思考题链式栈的入栈和出栈为什么选择在头部操作如果在尾部操作会怎样括号匹配算法中如果表达式中包含其他字符如字母、数字为什么可以直接忽略下面这个字符串能匹配吗为什么({[}])尝试实现一个函数判断HTML标签是否匹配如divp/p/div。欢迎在评论区讨论你的答案。