20. 栈与队列的指针实现：基于动态数组的栈、基于链表的队列

栈和队列，这两个数据结构，说白了就是「受限的线性表」。

我刚开始学的时候，觉得它们不就是数组加几个指针嘛，有啥好讲的？后来在嵌入式项目里写任务调度器，才发现一个不小心，栈溢出能把整个系统搞崩。嗯，那时候我才真正理解——指针怎么指，决定了你的程序是稳如老狗，还是随时翻车。

20.1 栈：后进先出，用动态数组实现

栈的特点，你肯定知道：后进先出（LIFO）。就像一摞盘子，你只能从最上面拿。

用动态数组实现栈，核心就三个东西：一块连续内存、一个栈顶指针、一个容量标记。

核心要点：栈顶指针永远指向「下一个空闲位置」，而不是当前栈顶元素。这是我个人习惯，也是很多工业代码的写法。为什么？因为判空和判满的逻辑更统一。

20.1.1 结构定义

typedef struct {
    int *data;      // 动态数组基地址
    int top;        // 栈顶指针（指向下一个空闲位置）
    int capacity;   // 当前容量
} Stack;

这里要注意：top 初始化为 0，表示空栈。每压入一个元素，top++；每弹出一个，top--。

20.1.2 初始化与销毁

Stack* createStack(int initCapacity) {
    Stack *s = (Stack*)malloc(sizeof(Stack));
    if (!s) return NULL;
    s->data = (int*)malloc(sizeof(int) * initCapacity);
    if (!s->data) {
        free(s);
        return NULL;
    }
    s->top = 0;
    s->capacity = initCapacity;
    return s;
}

void destroyStack(Stack *s) {
    if (s) {
        free(s->data);
        free(s);
    }
}

我曾经在项目里犯过一个低级错误：只 free 了 Stack 结构体，忘了 free 内部的 data 数组。结果内存泄漏，跑了三天系统变慢。嗯，谁还没漏过几次 free 呢？

20.1.3 压栈与弹栈

int push(Stack *s, int value) {
    if (s->top >= s->capacity) {
        // 扩容：我习惯每次翻倍，减少 realloc 次数
        int newCap = s->capacity * 2;
        int *newData = (int*)realloc(s->data, sizeof(int) * newCap);
        if (!newData) return -1;
        s->data = newData;
        s->capacity = newCap;
    }
    s->data[s->top++] = value;
    return 0;
}

int pop(Stack *s, int *out) {
    if (s->top == 0) return -1;  // 空栈
    *out = s->data[--s->top];
    return 0;
}

避坑指南：弹栈时，我见过有人把 --s->top 写成 s->top--。你想想看，如果先取 top 再减，拿到的就是「下一个空闲位置」的垃圾值。这种 bug 很难查，因为大部分时候栈里刚好有旧数据，看起来好像是对的……直到某次数据被覆盖。

20.2 队列：先进先出，用链表实现

队列就是排队。先来的先服务，后来的后服务。用链表实现队列，天然适合——你只需要记住头和尾。

20.2.1 结构定义

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *front;  // 队头指针
    Node *rear;   // 队尾指针
    int size;     // 队列长度
} Queue;

为什么不用数组实现队列？因为数组出队要移动元素，效率低。链表只需要改两个指针，O(1)。

20.2.2 入队与出队

int enqueue(Queue *q, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) return -1;
    newNode->data = value;
    newNode->next = NULL;

    if (q->rear == NULL) {
        // 空队列
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    q->size++;
    return 0;
}

int dequeue(Queue *q, int *out) {
    if (q->front == NULL) return -1;  // 空队列
    Node *temp = q->front;
    *out = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;  // 队列变空，rear 也要置空
    }
    free(temp);
    q->size--;
    return 0;
}

注意：出队时，如果队列只剩一个节点，front 和 rear 都指向它。出队后 front 变成 NULL，但 rear 还指向那个已经被 free 的节点。这就是经典的「野指针」问题。我调试过一个类似的 bug，花了整整一个下午——最后发现就是少了一句 q->rear = NULL。

20.3 知识体系：指针在栈与队列中的角色

下面这张图，是我自己梳理的。你看完应该能明白，指针到底在管什么。

栈与队列的指针实现核心逻辑 栈（动态数组） • data 指针 → 堆上连续内存 • top 指针（整数索引） • capacity 控制扩容时机 push: data[top++] = value pop: *out = data[--top] ⚠ 扩容时 realloc 可能移动内存 ⚠ top 指向下一个空闲位置 队列（链表） • front 指针 → 队头节点 • rear 指针 → 队尾节点 • size 记录节点数量 enqueue: rear->next = newNode dequeue: front = front->next ⚠ 出队后若队列为空，rear 要置 NULL ⚠ 每个节点独立 malloc/free 指针就是「连接」—— 连接内存块，连接节点，连接过去和未来

20.4 性能对比：什么时候选哪个？

操作 动态数组栈 链表队列
入栈/入队 O(1) 均摊（扩容时 O(n)） O(1)
出栈/出队 O(1) O(1)
内存碎片 低（连续内存） 高（每个节点独立分配）
适合场景 函数调用、表达式求值 消息队列、BFS、任务调度

我个人习惯：如果数据量可预估且稳定，用动态数组栈。如果数据量波动大、或者需要频繁插入删除，链表队列更灵活。你想想看，嵌入式里消息队列几乎全是链表实现的——因为你不知道下一秒会来多少条消息。

一个小技巧：如果你用动态数组实现队列，可以用「循环队列」——通过取模运算复用数组空间。但要注意区分「空」和「满」两种状态。我一般多留一个空位，或者用 size 字段辅助判断。

20.5 总结

栈和队列，说到底就是「指针的艺术」。

  • 栈用 top 指针控制「压」和「弹」的边界。
  • 队列用 front 和 rear 两个指针维护「先进先出」的顺序。
  • 动态数组扩容要小心 realloc 后的指针失效。
  • 链表节点释放后，记得把相关指针置 NULL。

嗯，这些坑我都踩过。你记住了，就能少走弯路。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →