/* 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 章的链表（头插头弹），接口一行不改——这就是接口分离的红利。
/* 循环数组实现：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;
}顺序数组出队会把前端空间浪费掉，循环取模让数组首尾相接复用空间——硬件环形缓冲区（串口收发）同款思路。链表实现则一头进一头出，无需预分配。
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/红黑）救场——思想相同，多了旋转。