这一章在干嘛？
用前面全部家底（结构、指针、动态内存、函数指针）实现三个经典 ADT。重点不在背代码，而在体会「接口与实现分离」的工程思想——头文件给接口，.c 藏细节。
17.1 堆栈：后进先出
/* stack.h —— 接口（调用者只见这个） */
void stack_push(int v); /* 压栈 */
int stack_pop(void); /* 弹栈并返回；空栈调用是契约违约 */
int stack_is_empty(void);
/* stack.c —— 实现 1：定长数组（静态） */
#define CAPACITY 100
static int stack[CAPACITY]; /* static：模块私有，外界摸不到 */
static int top; /* 栈顶游标（下一个空位） */
void stack_push(int v)
{
assert(top < CAPACITY); /* 满栈是实现bug或契约违约 */
stack[top++] = v;
}
int stack_pop(void)
{
assert(top > 0);
return stack[--top];
}
int stack_is_empty(void) { return top == 0; }
数组版简单高效但容量定死；把 static int stack 换成 malloc 动态数组 + 扩容，或换成第 12 章的链表（头插头弹），接口一行不改——这就是接口分离的红利。
17.2 队列：先进先出
/* 循环数组实现：front 出、rear 进，下标对容量取模 */
static int queue[CAPACITY];
static size_t front, count; /* count 免得区分空/满 */
void queue_enqueue(int v)
{
assert(count < CAPACITY);
queue[(front + count) % CAPACITY] = v;
count++;
}
int queue_dequeue(void)
{
assert(count > 0);
int v = queue[front];
front = (front + 1) % CAPACITY; /* 出队后 front 前移 */
count--;
return v;
}
顺序数组出队会把前端空间浪费掉，循环取模让数组首尾相接复用空间——硬件环形缓冲区（串口收发）同款思路。链表实现则一头进一头出，无需预分配。
17.3 二叉搜索树：有序数据的查找利器
typedef struct TreeNode {
int value;
struct TreeNode *left; /* 全部 < 本节点 */
struct TreeNode *right; /* 全部 > 本节点 */
} TreeNode;
/* 递归插入：返回（可能的）新子树根 */
TreeNode *bst_insert(TreeNode *root, int v)
{
if (root == NULL) {
root = malloc(sizeof *root);
if (root) { root->value = v; root->left = root->right = NULL; }
return root;
}
if (v < root->value) root->left = bst_insert(root->left, v);
else if (v > root->value) root->right = bst_insert(root->right, v);
/* v == 已存在：不插 */
return root;
}
/* 中序遍历 = 升序输出；前中后序只差「访问自己」的位置 */
void bst_inorder(const TreeNode *root)
{
if (root == NULL) return;
bst_inorder(root->left);
printf("%d ", root->value);
bst_inorder(root->right);
}
| 操作 | 平均复杂度 | 最坏（退化成链） |
|---|---|---|
| 查找 / 插入 | O(log n) | O(n)（按序插入树失衡） |
| 删除节点 | 找右子树最小值补位 | O(n) |
删除的三个情形：叶子直接摘；单子树让子树上移顶替；双子树用「右子树最小值（或左子树最大值）」换值后再删那个替身。按序插入会退化成链表，工程上用平衡树（AVL/红黑）救场——思想相同，多了旋转。
本章通关标准：
说得出堆栈/队列各自「进出」规则与典型应用（函数调用栈、撤销栈 / 打印队列、缓冲区）；能手写 BST 的递归插入和中序遍历；理解接口与实现分离给「换底层」留的活口。
1. 循环队列为什么用 (front + count) % CAPACITY？
数组队列反复出入队会让前端空间废弃。取模让下标绕回首尾相接；用 count 计数避免「front==rear 时分不清空还是满」的二义性。串口/网络收发缓冲区同款结构。
2. 二叉搜索树的中序遍历为什么正好升序？
BST 性质：左子树全部小于节点、右子树全部大于节点。中序遍历顺序是「左-根-右」，递归展开后每个节点都在其左子树之后、右子树之前被访问，恰好就是从小到大的序列。
3. BST 删除双子树节点怎么办？
用右子树的最小值（最左节点）替换被删节点的值，然后去右子树里删掉那个替身节点（替身必无左孩子，落入简单情形）。用左子树最大值同理。这样保持 BST 有序性质不变。