20、动态栈：用动态数组实现栈、压栈与出栈操作

栈这种数据结构，说白了就是「后进先出」。你想想看，就像一摞盘子，你总是先拿最上面那个。在C语言里，栈的实现方式有两种：静态数组和动态数组。我个人更偏爱动态数组的方式，因为它在运行时能灵活伸缩，不会像静态数组那样，一开始就得定死大小。

我记得刚入行那会儿，有个同事用静态数组实现栈，结果程序跑着跑着就栈溢出了。排查了半天，发现是业务数据量突然增大，栈容量不够了。从那以后，我但凡写栈，必用动态数组。今天咱们就来聊聊这个。

栈的核心结构

动态栈，本质上就是一个动态数组加上一个栈顶指针。我习惯这样定义结构体：

typedef struct {
    int *data;      // 动态数组的基地址
    int top;        // 栈顶索引，-1表示空栈
    int capacity;   // 当前容量
} DynamicStack;

这里有个细节：top 初始化为 -1。为什么？因为空栈时没有元素，索引 -1 刚好表示「栈顶在数组之外」。压入第一个元素时，top 变成 0，元素放在 data[0] 位置。嗯，这个设计很自然。

初始化与销毁

初始化时，我一般先分配一个较小的初始容量。比如 4 个元素。太小了频繁扩容，太大了浪费内存。4 是个不错的起点。

void initStack(DynamicStack *s) {
    s->capacity = 4;
    s->data = (int*)malloc(s->capacity * sizeof(int));
    if (s->data == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    s->top = -1;
}

销毁时，别忘了释放内存。我曾经见过有人只把 top 置为 -1，却不 free data，结果内存泄漏了。嗯，这个坑我踩过。

void destroyStack(DynamicStack *s) {
    free(s->data);
    s->data = NULL;
    s->top = -1;
    s->capacity = 0;
}

压栈操作

压栈前，先检查容量是否已满。如果满了，就扩容。扩容策略我一般用「翻倍」——容量乘以 2。为什么翻倍？因为这样均摊下来，每次压栈的时间复杂度是 O(1)。如果每次只加 1 个位置，那频繁 realloc 会拖慢性能。

void push(DynamicStack *s, int value) {
    if (s->top == s->capacity - 1) {
        s->capacity *= 2;
        s->data = (int*)realloc(s->data, s->capacity * sizeof(int));
        if (s->data == NULL) {
            printf("扩容失败\n");
            exit(1);
        }
    }
    s->top++;
    s->data[s->top] = value;
}

小技巧：realloc 可能会移动内存块，所以原来的指针会失效。但 realloc 内部会帮你拷贝旧数据，你只管用新指针就行。不过要注意，realloc 失败时返回 NULL，但原来的内存块不会被释放。所以最好用一个临时指针接收返回值，避免原指针丢失。

出栈操作

出栈就简单了。先判断栈是否为空，不为空就把 top 减 1。注意，我们并不真的删除 data[top] 里的值，只是把 top 往下移。下次压栈时，新值会覆盖旧值。

int pop(DynamicStack *s) {
    if (s->top == -1) {
        printf("栈已空，无法出栈\n");
        return -1;  // 实际项目中建议用错误码或异常处理
    }
    int value = s->data[s->top];
    s->top--;
    return value;
}

注意：出栈时要不要缩容？我个人建议不要频繁缩容。如果业务场景中栈的大小波动很大，可以在出栈后检查一下：如果当前元素数量小于容量的 1/4，就缩容到一半。这样可以避免「压一个就扩容，出一个就缩容」的抖动问题。

完整示例

下面是一个完整的 demo，演示了压栈和出栈的全过程：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;
    int top;
    int capacity;
} DynamicStack;

void initStack(DynamicStack *s) {
    s->capacity = 4;
    s->data = (int*)malloc(s->capacity * sizeof(int));
    if (!s->data) { printf("分配失败\n"); exit(1); }
    s->top = -1;
}

void push(DynamicStack *s, int v) {
    if (s->top == s->capacity - 1) {
        s->capacity *= 2;
        s->data = (int*)realloc(s->data, s->capacity * sizeof(int));
        if (!s->data) { printf("扩容失败\n"); exit(1); }
    }
    s->data[++s->top] = v;
}

int pop(DynamicStack *s) {
    if (s->top == -1) { printf("空栈\n"); return -1; }
    return s->data[s->top--];
}

void printStack(DynamicStack *s) {
    printf("栈内容(从底到顶): ");
    for (int i = 0; i <= s->top; i++) {
        printf("%d ", s->data[i]);
    }
    printf("\n");
}

int main() {
    DynamicStack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);
    printStack(&s);  // 10 20 30

    printf("出栈: %d\n", pop(&s)); // 30
    printStack(&s);  // 10 20

    push(&s, 40);
    push(&s, 50);
    printStack(&s);  // 10 20 40 50

    destroyStack(&s);
    return 0;
}

动态栈的核心逻辑图

下面这张 SVG 图，帮你理清动态栈的运作流程：

动态栈核心逻辑 动态数组 data[0] = 10 data[1] = 20 data[2] = 30 ← top data[3] = 空 ... 后续空间 操作流程 压栈 (push): 1. 检查 top == capacity-1 ? 2. 若满 → 扩容 (capacity *= 2) 3. top++ 4. data[top] = value 出栈 (pop): 1. 检查 top == -1 ? 2. 若空 → 报错 3. value = data[top] 4. top-- 5. return value

常见问题与避坑

  • 内存泄漏：每次 malloc/realloc 后，一定要检查返回值。我曾经在项目中忘了检查 realloc 返回值，结果内存不足时程序直接崩溃。后来加上了检查，稳多了。
  • 栈顶指针越界：压栈时先判断容量，出栈时先判断是否为空。这两个检查缺一不可。我见过有人只检查容量不检查空栈，结果 pop 了一个空栈，返回了垃圾数据。
  • 缩容策略：不要每次出栈都缩容。我建议当元素数量小于容量的 1/4 时，才缩容到一半。这样可以避免频繁 realloc。

核心要点：动态栈的本质就是「动态数组 + 栈顶指针」。压栈时扩容，出栈时缩容（可选）。时间复杂度均摊 O(1)，空间复杂度 O(n)。记住：先检查，再操作，最后释放。

好了，动态栈的内容就这些。你可以在自己的项目里试试，把静态数组换成动态数组，感受一下灵活性的提升。嗯，动手写一遍，比看十遍都管用。

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

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