1. 栈：叠盘子的「FILO哲学」
小白困惑：栈的“先进后出”到底怎么用？顺序栈和链式栈如何选择？
生活类比：
顺序栈 ≈ 固定大小的盘子架（需预判最大容量）
链式栈 ≈ 无限叠放的盘子（动态扩展，但需手动管理指针）
入栈（Push） ≈ 放新盘子到顶部
出栈（Pop） ≈ 从顶部取盘子
代码对比：
顺序栈（数组实现）：
typedef struct {
int *data; // 盘子架
int top; // 当前顶部盘子位置
int capacity; // 最大容量
} SeqStack;
void push(SeqStack *s, int value) {
if (s->top == s->capacity - 1) {
printf("盘子架已满！\n"); // 必须判满！
return;
}
s->data[++s->top] = value; // 顶部指针先+1，再放盘子
}
链式栈（动态内存）：
typedef struct Node {
int data;
struct Node *next;
} LinkStack;
void push(LinkStack **top, int value) {
LinkStack *new_node = (LinkStack*)malloc(sizeof(LinkStack));
new_node->data = value;
new_node->next = *top; // 新盘子指向当前顶部
*top = new_node; // 更新顶部指针
}
关键点：链式栈无需预判容量，但每次操作需处理指针关系！
2. 避坑指南：栈操作的「三大纪律」
1️⃣ 顺序栈未判满：盘子架溢出
// 错误！未检查容量导致数据覆盖
void push_bug(SeqStack *s, int value) {
s->data[s->top++] = value; // top可能越界！
}
2️⃣ 链式栈未置空指针：悬挂的盘子
// 正确写法
int pop(LinkStack **top) {
if (*top == NULL) return -1; // 判空
LinkStack *temp = *top;
int value = temp->data;
*top = (*top)->next; // 更新顶部
free(temp); // 释放内存
temp = NULL; // 防止野指针
return value;
}
3️⃣ 混淆栈顶指针含义：
顺序栈中top通常指向最后一个有效元素（初始为-1）
链式栈中top直接指向栈顶节点
3. 队列：餐厅排队的「FIFO法则」
场景：实现循环队列（解决假溢出问题）
生活类比：
循环队列 ≈ 环形餐桌（尾指针追上头指针即为满）
牺牲一个空间：避免头尾指针重合时的歧义
代码实现：
typedef struct {
int *data; // 环形缓冲区
int front; // 队头（第一个元素）
int rear; // 队尾（最后一个元素的下一个位置）
int capacity; // 总容量（实际可用capacity-1）
} CircularQueue;
void enqueue(CircularQueue *q, int value) {
if ((q->rear + 1) % q->capacity == q->front) {
printf("餐桌已满，请排队！\n");
return;
}
q->data[q->rear] = value;
q->rear = (q->rear + 1) % q->capacity; // 环形移动
}
关键点：rear指向的位置永远为空，用于区分队列满和空！
4. 双向链表：地铁车厢的「双门连接」
场景：实现约瑟夫环问题（动态删除节点）
生活类比：
双向链表 ≈ 地铁车厢（每节车厢有前后门，可双向移动）
约瑟夫环 ≈ 乘客围成圈，数到指定号码者下车
代码精简：
typedef struct Node {
int data;
struct Node *prev;
struct Node *next;
} DNode;
void josephus(int n, int k, int m) {
DNode *head = NULL, *p = NULL;
// 构建双向循环链表
for (int i = 1; i <= n; i++) {
DNode *new_node = (DNode*)malloc(sizeof(DNode));
new_node->data = i;
if (head == NULL) {
head = new_node;
head->next = head->prev = head;
} else {
p = head->prev; // 找到尾节点
p->next = new_node;
new_node->prev = p;
new_node->next = head;
head->prev = new_node;
}
}
// 开始删除
p = head;
while (p->next != p) {
for (int i = 1; i < m; i++)
p = p->next;
DNode *victim = p;
p = p->next;
victim->prev->next = victim->next;
victim->next->prev = victim->prev;
printf("出局：%d\n", victim->data);
free(victim);
}
printf("幸存者：%d\n", p->data);
}
终极挑战：用栈实现队列
要求：仅用两个栈模拟队列的FIFO特性
代码框架：
typedef struct {
SeqStack s1; // 主栈（用于入队）
SeqStack s2; // 辅助栈（用于出队）
} StackQueue;
void enqueue(StackQueue *q, int value) {
push(&q->s1, value); // 直接压入s1
}
int dequeue(StackQueue *q) {
if (isEmpty(&q->s2)) {
while (!isEmpty(&q->s1)) {
push(&q->s2, pop(&q->s1)); // 将s1倒入s2
}
}
return pop(&q->s2); // 从s2弹出
}
原理：
入队时直接压入s1。
出队时若s2为空，则将s1元素全部倒入s2，实现顺序反转。
避坑清单
栈溢出：顺序栈必须预判容量，链式栈检查malloc返回值。
队列假满：循环队列牺牲一个空间，区分front == rear的空/满状态。
双向链表断链：删除节点时需同时调整prev和next指针。
内存泄漏：链式结构每次删除后需free并置空指针。