栈

栈 (Stack)

后进先出（LIFO）数据结构。支持数组实现和链表实现两种方案。

---

数组实现

结构定义

typedef struct {
    int *data;
    size_t top;       /* 栈顶下标（指向下一个空位） */
    size_t capacity;
} AStack;

函数签名

函数	复杂度	说明
void astack_init(AStack *s, size_t cap)	O(1)	初始化
void astack_push(AStack *s, int val)	均摊 O(1)	压栈
int astack_pop(AStack *s)	O(1)	弹栈（空栈调用属未定义行为）
int astack_top(AStack *s)	O(1)	查看栈顶
int astack_empty(AStack *s)	O(1)	判空
void astack_free(AStack *s)	O(1)	释放

优点：缓存友好、无额外指针开销。缺点：最大容量受内存限制，pop 不释放内存（需手动缩容）。

---

链表实现

结构定义

typedef struct SNode {
    int data;
    struct SNode *next;
} SNode;
 
typedef struct {
    SNode *top;
    size_t size;
} LStack;

函数签名

函数	复杂度	说明
void lstack_init(LStack *s)	O(1)	初始化
void lstack_push(LStack *s, int val)	O(1)	头插压栈
int lstack_pop(LStack *s)	O(1)	头删弹栈
int lstack_top(LStack *s)	O(1)	查看栈顶

优点：无容量限制，pop 自动释放内存。缺点：缓存不友好，每个元素多一个指针开销。

---

使用模式

AStack s;
astack_init(&s, 16);
astack_push(&s, 10);
astack_push(&s, 20);
printf("%d\n", astack_top(&s));   /* 20 */
astack_pop(&s);
/* 栈中: [10] */
astack_free(&s);

---

典型应用

• 函数调用栈（递归的底层机制）
• 表达式求值（中缀转后缀）
• 括号匹配
• 深度优先搜索（DFS）
• 浏览器的前进/后退

---

跨语言参考

• C语言数据结构：栈