C语言栈实战5个经典算法问题代码解析与深度优化在计算机科学中栈Stack是一种基础但强大的数据结构它遵循后进先出LIFO的原则。本文将深入探讨栈在C语言中的实际应用通过五个经典算法问题的完整代码实现帮助读者掌握栈的核心思想并提升编程能力。1. 括号匹配问题括号匹配是栈最典型的应用场景之一。我们需要检查一个字符串中的括号是否完全匹配包括圆括号()、方括号[]和花括号{}。#include stdio.h #include stdlib.h #include stdbool.h #include string.h #define MAX_SIZE 100 typedef struct { char data[MAX_SIZE]; int top; } Stack; void initStack(Stack *s) { s-top -1; } bool isEmpty(Stack *s) { return s-top -1; } bool push(Stack *s, char c) { if (s-top MAX_SIZE - 1) return false; s-data[s-top] c; return true; } char pop(Stack *s) { if (isEmpty(s)) return \0; return s-data[s-top--]; } bool isMatchingPair(char opening, char closing) { return (opening ( closing )) || (opening [ closing ]) || (opening { closing }); } bool checkParentheses(const char *expr) { Stack s; initStack(s); for (int i 0; expr[i] ! \0; i) { if (expr[i] ( || expr[i] [ || expr[i] {) { push(s, expr[i]); } else if (expr[i] ) || expr[i] ] || expr[i] }) { if (isEmpty(s) || !isMatchingPair(pop(s), expr[i])) { return false; } } } return isEmpty(s); } int main() { const char *test1 ({[]}); const char *test2 ({[}]); printf(Test1 is %s\n, checkParentheses(test1) ? valid : invalid); printf(Test2 is %s\n, checkParentheses(test2) ? valid : invalid); return 0; }优化点分析使用数组实现栈操作时间复杂度为O(1)添加了栈满检查防止缓冲区溢出支持三种括号类型的匹配检查代码结构清晰函数职责单一2. 表达式求值中缀转后缀栈在表达式求值中扮演着关键角色特别是将中缀表达式转换为后缀表达式逆波兰表示法。#include stdio.h #include ctype.h #include string.h #define MAX_SIZE 100 typedef struct { char data[MAX_SIZE]; int top; } CharStack; void initCharStack(CharStack *s) { s-top -1; } bool isCharStackEmpty(CharStack *s) { return s-top -1; } bool pushChar(CharStack *s, char c) { if (s-top MAX_SIZE - 1) return false; s-data[s-top] c; return true; } char popChar(CharStack *s) { if (isCharStackEmpty(s)) return \0; return s-data[s-top--]; } char peekChar(CharStack *s) { if (isCharStackEmpty(s)) return \0; return s-data[s-top]; } int precedence(char op) { switch(op) { case : case -: return 1; case *: case /: return 2; case ^: return 3; default: return 0; } } void infixToPostfix(const char *infix, char *postfix) { CharStack s; initCharStack(s); int j 0; for (int i 0; infix[i] ! \0; i) { if (isalnum(infix[i])) { postfix[j] infix[i]; } else if (infix[i] () { pushChar(s, infix[i]); } else if (infix[i] )) { while (!isCharStackEmpty(s) peekChar(s) ! () { postfix[j] popChar(s); } popChar(s); // 弹出 ( } else { // 运算符 while (!isCharStackEmpty(s) precedence(peekChar(s)) precedence(infix[i])) { postfix[j] popChar(s); } pushChar(s, infix[i]); } } while (!isCharStackEmpty(s)) { postfix[j] popChar(s); } postfix[j] \0; } int main() { const char *infix ab*(c^d-e)^(fg*h)-i; char postfix[MAX_SIZE]; infixToPostfix(infix, postfix); printf(Infix: %s\nPostfix: %s\n, infix, postfix); return 0; }关键点解析运算符优先级处理^*/-括号的特殊处理遇到右括号时弹出栈中元素直到匹配到左括号输出数字和字母直接作为操作数最终弹出栈中所有剩余运算符3. 迷宫求解问题栈可以用于回溯算法如迷宫求解。我们使用深度优先搜索DFS策略利用栈记录路径。#include stdio.h #include stdbool.h #define ROWS 5 #define COLS 5 typedef struct { int x, y; } Point; typedef struct { Point data[ROWS * COLS]; int top; } PointStack; void initPointStack(PointStack *s) { s-top -1; } bool pushPoint(PointStack *s, Point p) { if (s-top ROWS * COLS - 1) return false; s-data[s-top] p; return true; } Point popPoint(PointStack *s) { Point p {-1, -1}; if (s-top -1) return p; return s-data[s-top--]; } bool isPointStackEmpty(PointStack *s) { return s-top -1; } bool isValid(int maze[ROWS][COLS], int x, int y, bool visited[ROWS][COLS]) { return x 0 x ROWS y 0 y COLS maze[x][y] 1 !visited[x][y]; } bool solveMaze(int maze[ROWS][COLS], Point start, Point end) { bool visited[ROWS][COLS] {false}; PointStack path; initPointStack(path); pushPoint(path, start); visited[start.x][start.y] true; // 四个可能的移动方向上、右、下、左 int dx[] {-1, 0, 1, 0}; int dy[] {0, 1, 0, -1}; while (!isPointStackEmpty(path)) { Point current popPoint(path); if (current.x end.x current.y end.y) { pushPoint(path, current); // 将终点重新压入栈 printf(Path found:\n); // 打印路径 PointStack temp; initPointStack(temp); while (!isPointStackEmpty(path)) { pushPoint(temp, popPoint(path)); } while (!isPointStackEmpty(temp)) { Point p popPoint(temp); printf((%d, %d) , p.x, p.y); } printf(\n); return true; } for (int i 0; i 4; i) { int newX current.x dx[i]; int newY current.y dy[i]; if (isValid(maze, newX, newY, visited)) { Point next {newX, newY}; pushPoint(path, current); pushPoint(path, next); visited[newX][newY] true; break; // 深度优先先探索一个方向 } } } printf(No path found\n); return false; } int main() { int maze[ROWS][COLS] { {1, 0, 1, 1, 1}, {1, 1, 1, 0, 1}, {0, 0, 0, 1, 1}, {1, 0, 0, 1, 0}, {1, 1, 1, 1, 1} }; Point start {0, 0}; Point end {4, 4}; solveMaze(maze, start, end); return 0; }算法特点使用深度优先搜索策略栈用于记录当前路径访问标记数组防止重复访问找到解时逆向打印路径4. 浏览器前进后退功能模拟栈可以完美模拟浏览器的前进后退功能使用两个栈分别记录访问历史和后撤记录。#include stdio.h #include stdlib.h #include string.h #include stdbool.h #define MAX_PAGES 100 #define MAX_URL_LENGTH 100 typedef struct { char data[MAX_PAGES][MAX_URL_LENGTH]; int top; } BrowserStack; void initBrowserStack(BrowserStack *s) { s-top -1; } bool isBrowserStackEmpty(BrowserStack *s) { return s-top -1; } bool isBrowserStackFull(BrowserStack *s) { return s-top MAX_PAGES - 1; } bool pushBrowserStack(BrowserStack *s, const char *url) { if (isBrowserStackFull(s)) return false; strcpy(s-data[s-top], url); return true; } bool popBrowserStack(BrowserStack *s, char *url) { if (isBrowserStackEmpty(s)) return false; strcpy(url, s-data[s-top--]); return true; } bool peekBrowserStack(BrowserStack *s, char *url) { if (isBrowserStackEmpty(s)) return false; strcpy(url, s-data[s-top]); return true; } typedef struct { BrowserStack backStack; BrowserStack forwardStack; char currentPage[MAX_URL_LENGTH]; } Browser; void initBrowser(Browser *browser, const char *homepage) { initBrowserStack(browser-backStack); initBrowserStack(browser-forwardStack); strcpy(browser-currentPage, homepage); } void visit(Browser *browser, const char *url) { pushBrowserStack(browser-backStack, browser-currentPage); strcpy(browser-currentPage, url); // 访问新页面时清空前进栈 browser-forwardStack.top -1; printf(Visited: %s\n, url); } bool back(Browser *browser) { if (isBrowserStackEmpty(browser-backStack)) { printf(Cannot go back\n); return false; } pushBrowserStack(browser-forwardStack, browser-currentPage); popBrowserStack(browser-backStack, browser-currentPage); printf(Back to: %s\n, browser-currentPage); return true; } bool forward(Browser *browser) { if (isBrowserStackEmpty(browser-forwardStack)) { printf(Cannot go forward\n); return false; } pushBrowserStack(browser-backStack, browser-currentPage); popBrowserStack(browser-forwardStack, browser-currentPage); printf(Forward to: %s\n, browser-currentPage); return true; } void printBrowserState(Browser *browser) { printf(\nCurrent Browser State:\n); printf(Current Page: %s\n, browser-currentPage); printf(Back Stack (Top at right): [); for (int i 0; i browser-backStack.top; i) { printf(%s, browser-backStack.data[i]); if (i browser-backStack.top) printf(, ); } printf(]\n); printf(Forward Stack (Top at right): [); for (int i 0; i browser-forwardStack.top; i) { printf(%s, browser-forwardStack.data[i]); if (i browser-forwardStack.top) printf(, ); } printf(]\n\n); } int main() { Browser browser; initBrowser(browser, homepage.com); visit(browser, page1.com); visit(browser, page2.com); visit(browser, page3.com); printBrowserState(browser); back(browser); back(browser); printBrowserState(browser); visit(browser, page4.com); printBrowserState(browser); forward(browser); // 应该失败 back(browser); forward(browser); printBrowserState(browser); return 0; }设计要点使用两个栈分别管理后退和前进功能访问新页面时清空前进栈提供状态打印函数方便调试处理边界情况空栈时的操作5. 函数调用栈模拟计算机系统中的函数调用正是基于栈的原理。我们可以用栈来模拟这一过程理解递归和函数调用的底层机制。#include stdio.h #include stdlib.h #include string.h #define MAX_STACK_SIZE 100 #define MAX_FUNC_NAME 50 typedef struct { char funcName[MAX_FUNC_NAME]; int returnAddress; int param1; int param2; int localVar1; int localVar2; } ActivationRecord; typedef struct { ActivationRecord data[MAX_STACK_SIZE]; int top; } CallStack; void initCallStack(CallStack *s) { s-top -1; } bool pushCallStack(CallStack *s, ActivationRecord ar) { if (s-top MAX_STACK_SIZE - 1) return false; s-data[s-top] ar; return true; } ActivationRecord popCallStack(CallStack *s) { ActivationRecord empty {, -1, 0, 0, 0, 0}; if (s-top -1) return empty; return s-data[s-top--]; } void printCallStack(CallStack *s) { printf(\nCurrent Call Stack (Top at bottom):\n); printf(| %-15s | %-5s | %-5s | %-5s | %-5s | %-5s |\n, Function, Ret, P1, P2, L1, L2); printf(|-----------------|-------|-------|-------|-------|-------|\n); for (int i 0; i s-top; i) { printf(| %-15s | %-5d | %-5d | %-5d | %-5d | %-5d |\n, s-data[i].funcName, s-data[i].returnAddress, s-data[i].param1, s-data[i].param2, s-data[i].localVar1, s-data[i].localVar2); } printf(\n); } // 模拟函数调用 int factorial(int n) { CallStack *cs malloc(sizeof(CallStack)); initCallStack(cs); // 模拟调用过程 ActivationRecord mainAR {main, -1, 0, 0, 0, 0}; pushCallStack(cs, mainAR); ActivationRecord factAR {factorial, 100, n, 0, 0, 0}; pushCallStack(cs, factAR); printCallStack(cs); int result 1; while (n 1) { factAR.localVar1 result; factAR.localVar2 n; cs-data[cs-top] factAR; // 模拟递归调用 ActivationRecord newFactAR {factorial, 200, n-1, 0, 0, 0}; pushCallStack(cs, newFactAR); printCallStack(cs); n--; result * n; popCallStack(cs); // 模拟返回 } factAR.localVar1 result; cs-data[cs-top] factAR; printCallStack(cs); popCallStack(cs); // 返回到main free(cs); return result; } int main() { printf(Calculating factorial(5)...\n); int result factorial(5); printf(Result: %d\n, result); return 0; }关键概念活动记录Activation Record包含函数执行所需的所有信息每次函数调用都会压入一个新的活动记录函数返回时弹出当前活动记录递归调用表现为同一函数的多个活动记录在栈中栈溢出可能发生在递归深度过大时栈的高级应用与性能优化在实际开发中栈的实现和选择需要考虑多种因素动态扩容栈实现#include stdio.h #include stdlib.h #include stdbool.h typedef struct { int *data; int top; int capacity; } DynamicStack; void initDynamicStack(DynamicStack *s, int initialCapacity) { s-data malloc(initialCapacity * sizeof(int)); s-top -1; s-capacity initialCapacity; } bool resizeDynamicStack(DynamicStack *s, int newCapacity) { int *newData realloc(s-data, newCapacity * sizeof(int)); if (!newData) return false; s-data newData; s-capacity newCapacity; return true; } bool pushDynamic(DynamicStack *s, int value) { if (s-top s-capacity - 1) { if (!resizeDynamicStack(s, s-capacity * 2)) { return false; } } s-data[s-top] value; return true; } bool popDynamic(DynamicStack *s, int *value) { if (s-top -1) return false; *value s-data[s-top--]; // 当栈大小小于容量的1/4时缩小容量为一半 if (s-top 0 s-top s-capacity / 4) { resizeDynamicStack(s, s-capacity / 2); } return true; } void freeDynamicStack(DynamicStack *s) { free(s-data); s-data NULL; s-top -1; s-capacity 0; }优化策略动态扩容当栈满时自动扩大容量动态缩容当栈使用率低于阈值时缩小容量倍增策略扩容时容量倍增减少频繁扩容安全释放提供专门的释放函数多栈共享同一存储空间在某些特殊场景下可能需要在一个数组中实现多个栈#include stdio.h #include stdbool.h #define TOTAL_SIZE 100 typedef struct { int data[TOTAL_SIZE]; int top1; int top2; } DoubleStack; void initDoubleStack(DoubleStack *s) { s-top1 -1; s-top2 TOTAL_SIZE; } bool push1(DoubleStack *s, int value) { if (s-top1 1 s-top2) return false; s-data[s-top1] value; return true; } bool push2(DoubleStack *s, int value) { if (s-top2 - 1 s-top1) return false; s-data[--s-top2] value; return true; } bool pop1(DoubleStack *s, int *value) { if (s-top1 -1) return false; *value s-data[s-top1--]; return true; } bool pop2(DoubleStack *s, int *value) { if (s-top2 TOTAL_SIZE) return false; *value s-data[s-top2]; return true; }应用场景内存有限时共享存储空间需要同时操作两个相关栈某些特殊算法需要双向栈操作栈的最小值跟踪设计一个栈支持push、pop和getMin操作且所有操作时间复杂度为O(1)#include stdio.h #include limits.h #define MAX_SIZE 100 typedef struct { int mainStack[MAX_SIZE]; int minStack[MAX_SIZE]; int top; } MinStack; void initMinStack(MinStack *s) { s-top -1; s-minStack[0] INT_MAX; } bool pushMin(MinStack *s, int value) { if (s-top MAX_SIZE - 1) return false; s-top; s-mainStack[s-top] value; // 更新最小值栈 if (value s-minStack[s-top]) { s-minStack[s-top 1] value; } else { s-minStack[s-top 1] s-minStack[s-top]; } return true; } bool popMin(MinStack *s, int *value) { if (s-top -1) return false; *value s-mainStack[s-top]; s-top--; return true; } int getMin(MinStack *s) { if (s-top -1) return INT_MAX; return s-minStack[s-top 1]; }算法分析使用辅助栈记录历史最小值每次push时同时更新最小值栈pop时无需额外操作getMin直接返回最小值栈顶元素通过这五个经典问题的深入解析和代码实现我们全面展示了栈在算法和实际应用中的强大能力。从基础的括号匹配到复杂的函数调用模拟栈提供了一种高效、直观的问题解决思路。理解这些应用场景和优化策略将大大提升你的编程能力和算法思维。