栈

栈是一种后进先出的数据结构，只能在一端进行插入和删除操作，后放入的数据会被优先取出。

January 1, 1968数据结构1分钟阅读

栈数据结构，Push 入栈向栈顶添加元素，Pop 出栈从栈顶移除元素，遵循后进先出。

想象一下桌上摞起来的一叠书，或者一筒羽毛球：

你最后放上去的那本书，总是最先被拿走。
你最先放进去的羽毛球，最后才能被取出来。

这就是栈的核心运作机制。

栈顶（Top）： 允许进行插入和删除操作的这一端（唯一能动的一端）。
栈底（Bottom）： 固定不动的一端。
空栈（Empty Stack）： 不含任何元素的栈。

栈的操作非常简洁，主要包含以下几种：

操作	英文	说明
入栈 / 压栈	`Push`	将一个新元素放入栈顶。
出栈 / 弹栈	`Pop`	移除并返回栈顶元素。
查看栈顶	`Peek` / `Top`	返回栈顶元素的值，但不出栈（栈的内容不变）。
判空	`IsEmpty`	检查栈内是否有元素。
获取大小	`Size`	返回当前栈中的元素个数。

栈通常可以通过以下两种方式来实现，各有优缺点：

使用连续的内存空间存储元素，用一个指针/变量 top 记录栈顶位置。

优点： 访问速度快，内存利用率高。
缺点： 如果是静态数组，容量受限；动态数组扩容时需要重新分配内存。

使用单链表实现，链头作为栈顶。

优点： 动态分配内存，不存在栈满溢出的问题（除非内存耗尽）。
缺点： 每个节点需要额外的指针空间，且节点分散在内存中，缓存命中率略低。

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100 // 固定容量

typedef struct {
    int data[MAX_SIZE];
    int top; // 栈顶下标，初始为 -1
} Stack;

// 初始化
void init(Stack *s) {
    s->top = -1;
}

// 压栈 (Push)
bool push(Stack *s, int val) {
    if (s->top >= MAX_SIZE - 1) return false; // 栈满
    s->data[++(s->top)] = val;
    return true;
}

// 弹栈 (Pop)
bool pop(Stack *s, int *val) {
    if (s->top < 0) return false; // 栈空
    *val = s->data[(s->top)--];
    return true;
}

// 使用示例
int main() {
    Stack s;
    init(&s);

    push(&s, 10);
    push(&s, 20);

    int val;
    pop(&s, &val); // val = 20
    printf("弹出的值: %d\n", val);

    return 0;
}

栈看似简单，但计算机底层和许多算法都高度依赖它：

程序调用函数时，系统会把当前函数的上下文（局部变量、返回地址等）压入栈中；函数执行完毕后再弹栈，恢复上层函数的执行。递归算法容易导致“栈溢出（Stack Overflow）”，就是因为压栈太多占满了内存。

访问新页面时压入“后退栈”；点击后退时，从后退栈弹出并压入“前进栈”。

文本编辑器中的 Ctrl + Z 就是把历史操作按栈的顺序依次回滚。

编译器在解析代码时，利用栈来检查括号是否成对闭合（如 { [ () ] }），或者将中缀表达式（1 + 2 * 3）转为后缀表达式进行计算。