数据结构入门：一文搞懂 “栈”
什么是栈？
栈（Stack）是一种简单又常用的数据结构，它的核心特点是 “后进先出”（LIFO，Last In First Out）。
可以用生活中 “叠盘子” 的例子理解：最后放到盘子堆最上面的盘子，会被最先拿走；最底下的盘子，要等上面所有盘子都拿走后才能被拿到。
栈的基本操作
栈有几个最核心的操作，就像我们对 “叠盘子” 能做的事：
- 入栈（Push）：把新元素放到栈的最顶端（就像新盘子放到最上面）
- 出栈（Pop）：把栈顶端的元素拿走（就像拿走最上面的盘子）
- 查看栈顶（Peek）：看看顶端是什么元素，但不拿走
- 判断空栈（isEmpty）：检查栈里有没有元素
- 判断满栈（isFull）：如果栈有固定大小，检查是否已经放满
用 C 语言实现栈（数组版）
我们用数组来实现栈，因为数组对初学者来说更直观。下面是完整代码，每个部分都有详细解释：
#include <stdio.h>
#include <stdlib.h>
// 定义栈的结构体
typedef struct Stack {
int* data; // 用数组存元素
int top; // 栈顶位置（索引），-1表示空栈
int capacity; // 栈的最大容量
} Stack;
// 1. 初始化栈：创建一个能存capacity个元素的栈
Stack* initStack(int capacity) {
// 给栈本身分配内存
Stack* stack = (Stack*)malloc(sizeof(Stack));
if (stack == NULL) {
printf("内存不够啦，创建栈失败！\n");
exit(1); // 退出程序
}
// 初始化栈的属性
stack->capacity = capacity; // 最大能存多少元素
stack->top = -1; // 初始为空栈（没有元素）
// 给存元素的数组分配内存
stack->data = (int*)malloc(capacity * sizeof(int));
if (stack->data == NULL) {
printf("内存不够啦，创建数组失败！\n");
free(stack); // 释放已分配的栈内存
exit(1);
}
return stack;
}
// 2. 判断栈是否为空
int isEmpty(Stack* stack) {
// 栈顶是-1，说明没有元素
return stack->top == -1;
}
// 3. 判断栈是否已满
int isFull(Stack* stack) {
// 栈顶位置等于最大容量-1，说明满了（因为数组索引从0开始）
return stack->top == stack->capacity - 1;
}
// 4. 入栈：把元素放到栈顶
void push(Stack* stack, int value) {
// 先检查栈是不是满了
if (isFull(stack)) {
printf("栈满了，%d 塞不进去啦！\n", value);
return;
}
// 栈顶位置+1，再把元素存进去
stack->top++;
stack->data[stack->top] = value;
printf("成功把 %d 放到栈顶\n", value);
}
// 5. 出栈：把栈顶元素拿走并返回
int pop(Stack* stack) {
// 先检查栈是不是空的
if (isEmpty(stack)) {
printf("栈是空的，没东西可拿！\n");
return -1; // 用-1表示错误（假设-1不是有效数据）
}
// 先记录栈顶元素，再把栈顶位置-1
int topValue = stack->data[stack->top];
stack->top--;
return topValue;
}
// 6. 查看栈顶元素（不拿走）
int peek(Stack* stack) {
if (isEmpty(stack)) {
printf("栈是空的，没元素可看！\n");
return -1;
}
return stack->data[stack->top];
}
// 7. 打印栈里的所有元素
void printStack(Stack* stack) {
if (isEmpty(stack)) {
printf("栈是空的～\n");
return;
}
printf("栈里的元素（从底到顶）：");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->data[i]);
}
printf("\n");
}
// 8. 销毁栈：释放内存（很重要，避免内存浪费）
void destroyStack(Stack* stack) {
free(stack->data); // 先释放存元素的数组
free(stack); // 再释放栈本身
printf("栈已销毁，内存释放完毕～\n");
}
// 主函数：演示栈的用法
int main() {
// 创建一个能存5个元素的栈
Stack* stack = initStack(5);
// 测试入栈
push(stack, 10); // 栈顶：10
push(stack, 20); // 栈顶：20（现在栈里是10,20）
push(stack, 30); // 栈顶：30（现在栈里是10,20,30）
printStack(stack); // 应该输出：10 20 30
printf("当前栈顶元素是：%d\n", peek(stack)); // 输出30
// 测试出栈
int popped = pop(stack);
printf("拿走了栈顶元素：%d\n", popped); // 拿走30
printStack(stack); // 现在剩下10,20
// 继续入栈，直到栈满
push(stack, 40);
push(stack, 50);
push(stack, 60); // 这是第5个元素，刚好满
push(stack, 70); // 栈满了，会提示失败
printStack(stack); // 输出：10 20 40 50 60
// 清空栈（全部出栈）
printf("清空栈：");
while (!isEmpty(stack)) {
printf("%d ", pop(stack));
}
printf("\n");
// 销毁栈
destroyStack(stack);
return 0;
}
代码逐句解释
1. 栈的结构体定义
typedef struct Stack {
int* data; // 数组：用来存栈里的元素
int top; // 栈顶位置：-1表示空栈，0表示有1个元素（索引从0开始）
int capacity; // 栈的最大容量：比如5表示最多存5个元素
} Stack;
这个结构体就像一个 “栈的说明书”，告诉我们栈需要哪些信息才能工作。
2. 初始化栈（initStack）
- 作用：创建一个新栈，分配内存并设置初始状态
- 关键：
top初始化为 - 1（空栈），data数组分配对应大小的内存
3. 入栈（push）
步骤：
- 检查栈是否已满（满了就塞不进去）
- 栈顶位置 + 1（
top++） - 把新元素存在
data[top]的位置
比如：初始 top=-1，push (10) 后，top=0，data[0]=10；再 push (20)，top=1，data[1]=20。
4. 出栈（pop）
步骤：
- 检查栈是否为空（空了就没东西可拿）
- 记录当前栈顶元素（
data[top]） - 栈顶位置 - 1（
top--） - 返回记录的元素
比如：栈里有 10、20（top=1），pop () 会返回 20，然后 top=0（现在栈顶是 10）。
5. 其他操作
isEmpty：通过top == -1判断是否为空isFull：通过top == capacity-1判断是否已满（因为数组索引从 0 开始）peek：直接返回data[top]（只看不动）destroyStack：必须手动释放内存，否则会造成内存泄漏
栈的运行结果
上面的 main函数运行后，会输出：
成功把 10 放到栈顶
成功把 20 放到栈顶
成功把 30 放到栈顶
栈里的元素（从底到顶）：10 20 30
当前栈顶元素是：30
拿走了栈顶元素：30
栈里的元素（从底到顶）：10 20
成功把 40 放到栈顶
成功把 50 放到栈顶
成功把 60 放到栈顶
栈满了，70 塞不进去啦！
栈里的元素（从底到顶）：10 20 40 50 60
清空栈：60 50 40 20 10
栈已销毁，内存释放完毕～
栈的实际应用
栈在编程中很常见，比如：
- 撤销操作：比如 Word 里的 “Ctrl+Z”，每一步操作都存在栈里，撤销时从栈顶取出上一步
- 括号匹配：判断代码里的
()、{}是否成对出现（用栈存左括号，遇到右括号就出栈匹配） - 函数调用：程序运行时，函数调用的顺序用栈管理（最后调用的函数先执行完返回）
评论区