栈：后进先出的数据结构
栈这个东西，说白了就是「后进先出」。你想想看，一摞盘子，你总是先拿最上面那个，后放上去的反而先被拿走。这就是栈的核心思想。
我在做嵌入式开发时，栈几乎无处不在。函数调用、中断处理、局部变量存储……底层全靠它撑着。不理解栈，你很难真正理解程序是怎么跑起来的。
栈的定义与特性
栈是一种操作受限的线性表。它只允许在一端进行插入和删除操作，这一端叫做栈顶，另一端叫栈底。
核心特性就两条：
- 后进先出（LIFO）：最后进去的元素，最先出来
- 操作受限：只能从栈顶操作，不能从中间插队
基本操作也很简单：
- push：压栈，把元素放到栈顶
- pop：出栈，把栈顶元素拿走
- peek/top：看一眼栈顶元素，但不拿走
- isEmpty：判断栈是不是空的
嗯，这里要注意：栈本身不关心元素是什么类型，它只关心「怎么放」和「怎么取」。至于里面存的是整数、字符还是结构体，那是你的事。
顺序栈的实现
顺序栈，就是用数组来实现栈。我个人习惯用这种方式，因为数组在内存中是连续的，访问速度快，嵌入式场景下很实用。
先看结构体定义：
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int top; // 栈顶指针，初始为 -1
} SeqStack;这里 top 指向当前栈顶元素的下标。空栈时 top = -1，每压入一个元素，top 先加 1，再赋值。
核心操作实现：
// 初始化
void initStack(SeqStack *s) {
s->top = -1;
}
// 判断是否为空
int isEmpty(SeqStack *s) {
return s->top == -1;
}
// 判断是否已满
int isFull(SeqStack *s) {
return s->top == MAX_SIZE - 1;
}
// 压栈
int push(SeqStack *s, int value) {
if (isFull(s)) {
return -1; // 栈满，返回错误
}
s->data[++(s->top)] = value;
return 0;
}
// 出栈
int pop(SeqStack *s, int *value) {
if (isEmpty(s)) {
return -1;
}
*value = s->data[(s->top)--];
return 0;
}
// 取栈顶
int peek(SeqStack *s, int *value) {
if (isEmpty(s)) {
return -1;
}
*value = s->data[s->top];
return 0;
}
注意：顺序栈有容量上限。我在项目中遇到过栈溢出导致系统崩溃的情况——中断嵌套太深，栈空间不够用了。所以嵌入式开发中，栈大小一定要算清楚。
链式栈的实现
链式栈就是用链表来实现栈。它没有容量限制，用多少就申请多少内存。但代价是每个节点多了一个指针域，内存开销更大。
结构体定义：
typedef struct Node {
int data;
struct Node *next;
} StackNode;
typedef struct {
StackNode *top; // 栈顶指针
int size; // 栈中元素个数
} LinkedStack;链式栈的压栈操作，其实就是链表的头插法：
void push(LinkedStack *s, int value) {
StackNode *node = (StackNode *)malloc(sizeof(StackNode));
if (node == NULL) {
return; // 内存分配失败
}
node->data = value;
node->next = s->top;
s->top = node;
s->size++;
}
int pop(LinkedStack *s, int *value) {
if (s->top == NULL) {
return -1; // 空栈
}
StackNode *temp = s->top;
*value = temp->data;
s->top = temp->next;
free(temp);
s->size--;
return 0;
}
我的建议：如果你能预估数据量，用顺序栈。如果数据量不确定，或者需要频繁创建销毁栈，用链式栈。嵌入式场景下，我倾向于顺序栈——没有动态内存分配，更可控。
栈的应用：括号匹配
这个场景太经典了。编译器检查你的代码括号是否成对，用的就是栈。
思路很简单：
- 遇到左括号（'('、'['、'{'），压栈
- 遇到右括号，检查栈顶是否匹配
- 如果匹配，弹出栈顶；不匹配，直接报错
- 遍历完所有字符后，栈应该是空的
int isMatching(char left, char right) {
return (left == '(' && right == ')') ||
(left == '[' && right == ']') ||
(left == '{' && right == '}');
}
int checkBrackets(const char *expr) {
SeqStack stack;
initStack(&stack);
for (int i = 0; expr[i] != '\0'; i++) {
char ch = expr[i];
if (ch == '(' || ch == '[' || ch == '{') {
push(&stack, ch);
} else if (ch == ')' || ch == ']' || ch == '}') {
int top;
if (pop(&stack, &top) != 0) {
return 0; // 栈空，右括号多余
}
if (!isMatching(top, ch)) {
return 0; // 不匹配
}
}
}
return isEmpty(&stack); // 栈空才正确
}我曾经在解析一个配置文件时，就因为括号不匹配导致整个系统启动失败。排查了半天，最后发现是一个花括号写成了方括号。嗯，从那以后我写代码都会顺手检查括号匹配。
栈的应用：表达式求值
表达式求值，说白了就是让计算机算数学算式。比如 "3 + 5 * 2"，你要算出 13，而不是 16。
这里的关键是运算符优先级。乘除优先于加减，括号内的优先计算。计算机怎么处理？用两个栈：
- 操作数栈：存数字
- 运算符栈：存运算符
算法流程：
- 遇到数字，压入操作数栈
- 遇到运算符，比较它与栈顶运算符的优先级：
- 如果当前运算符优先级更高，压栈
- 否则，弹出栈顶运算符，从操作数栈弹出两个数计算，结果压回操作数栈
- 遇到左括号，直接压栈
- 遇到右括号，一直计算直到遇到左括号
- 遍历完后，把运算符栈清空，依次计算
代码实现比较长，我贴核心部分：
int precedence(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}
int applyOp(int a, int b, char op) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
default: return 0;
}
}
int evaluate(const char *expr) {
SeqStack values; // 操作数栈
SeqStack ops; // 运算符栈
initStack(&values);
initStack(&ops);
for (int i = 0; expr[i] != '\0'; i++) {
if (expr[i] == ' ') continue;
if (isdigit(expr[i])) {
int val = 0;
while (isdigit(expr[i])) {
val = val * 10 + (expr[i] - '0');
i++;
}
push(&values, val);
i--;
} else if (expr[i] == '(') {
push(&ops, expr[i]);
} else if (expr[i] == ')') {
int op, a, b;
while (peek(&ops, &op) == 0 && op != '(') {
pop(&ops, &op);
pop(&values, &b);
pop(&values, &a);
push(&values, applyOp(a, b, op));
}
pop(&ops, &op); // 弹出 '('
} else {
int op;
while (!isEmpty(&ops) && peek(&ops, &op) == 0
&& precedence(op) >= precedence(expr[i])) {
pop(&ops, &op);
int a, b;
pop(&values, &b);
pop(&values, &a);
push(&values, applyOp(a, b, op));
}
push(&ops, expr[i]);
}
}
int op, a, b;
while (!isEmpty(&ops)) {
pop(&ops, &op);
pop(&values, &b);
pop(&values, &a);
push(&values, applyOp(a, b, op));
}
int result;
pop(&values, &result);
return result;
}
核心要点：表达式求值的本质就是「优先级管理」。栈在这里扮演了「记忆」的角色——先记住暂时不能算的运算符，等优先级更高的算完了再回头算它。
知识体系总览
下面这张图把栈的核心知识点串起来了：
栈这个东西，说简单也简单，说复杂也复杂。简单在于它的规则就那么几条，复杂在于它背后的应用场景千变万化。我做了这么多年嵌入式，栈始终是我最常用的数据结构之一。希望你能把它吃透，后面很多高级话题都离不开它。