栈与队列：用数组和链表实现后进先出与先进先出

说实话，栈和队列这两个数据结构，是我在嵌入式开发中用得最多的两个"容器"。你想想看，函数调用要用栈，消息传递要用队列，几乎每个像样点的系统都离不开它们。今天我们就来彻底搞明白，怎么用数组和链表分别实现这两种结构。

栈：后进先出的"弹夹"

栈的特点，说白了就是"先进去的最后出来"。我习惯把它想象成手枪的弹夹——你压进去的第一颗子弹在最底下，最后压进去的反而最先被推出去。这种结构在嵌入式里太常见了，比如函数调用的现场保护、中断嵌套的优先级处理，都是栈的典型应用。

用数组实现栈

数组实现栈，思路很直接。我们维护一个下标指针 top，指向栈顶元素的位置。入栈时 top++，出栈时 top--。嗯，这里要注意：数组大小是固定的，所以得提前想好最大深度。

#define MAX_STACK_SIZE 100

typedef struct {
    int data[MAX_STACK_SIZE];
    int top;  // 栈顶索引，-1表示空栈
} ArrayStack;

// 初始化
void initStack(ArrayStack *s) {
    s->top = -1;
}

// 入栈
int push(ArrayStack *s, int value) {
    if (s->top >= MAX_STACK_SIZE - 1) {
        return -1;  // 栈满
    }
    s->data[++(s->top)] = value;
    return 0;
}

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

// 查看栈顶
int peek(ArrayStack *s, int *value) {
    if (s->top == -1) return -1;
    *value = s->data[s->top];
    return 0;
}

我的经验：数组栈的优点是访问速度快，没有动态内存分配的开销。我在做单片机RTOS时，任务栈就用的数组实现——因为系统任务数量是编译期确定的，用数组反而更安全，不会出现内存碎片。

用链表实现栈

链表实现栈，其实就是在链表头部做插入和删除。每次入栈相当于头插一个新节点，出栈就是删除头节点。这样操作的时间复杂度是O(1)，而且不用担心栈满的问题——只要堆内存够用。

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

typedef struct {
    StackNode *top;  // 栈顶指针
} LinkedStack;

// 入栈（头插法）
int push(LinkedStack *s, int value) {
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    if (!newNode) return -1;
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
    return 0;
}

// 出栈（删除头节点）
int pop(LinkedStack *s, int *value) {
    if (!s->top) return -1;
    StackNode *temp = s->top;
    *value = temp->data;
    s->top = temp->next;
    free(temp);
    return 0;
}

我曾经踩过的坑：用链表实现栈时，一定要检查 malloc 的返回值。有一次我在一个内存紧张的项目里忘了检查，结果入栈失败时程序直接崩溃，查了半天才发现是堆空间耗尽了。嵌入式环境里，动态内存分配一定要谨慎再谨慎。

队列：先进先出的"管道"

队列和栈正好相反——先进去的先出来。我经常把它比作一根水管，你先灌进去的水先流出来。在嵌入式系统里，队列最常见的用途就是消息缓冲，比如串口接收数据、按键事件排队，都是靠队列来协调生产者和消费者的速度差异。

用数组实现循环队列

数组实现队列有个麻烦：如果只用头尾指针，出队后前面的空间就浪费了。解决办法是做成循环队列，让尾指针绕回来。判断队满的条件是 (rear + 1) % MAX_SIZE == front，这里故意空一个位置来区分队空和队满。

#define MAX_QUEUE_SIZE 10

typedef struct {
    int data[MAX_QUEUE_SIZE];
    int front;  // 队头索引
    int rear;   // 队尾索引
} CircularQueue;

// 初始化
void initQueue(CircularQueue *q) {
    q->front = 0;
    q->rear = 0;
}

// 入队
int enqueue(CircularQueue *q, int value) {
    if ((q->rear + 1) % MAX_QUEUE_SIZE == q->front) {
        return -1;  // 队满
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    return 0;
}

// 出队
int dequeue(CircularQueue *q, int *value) {
    if (q->front == q->rear) {
        return -1;  // 队空
    }
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return 0;
}

关键点：循环队列的 front 和 rear 都是下标，不是指针。队空时 front == rear，队满时 (rear+1)%N == front。这个"牺牲一个元素空间"的做法，是嵌入式里最常用的判断方式，简单可靠。

用链表实现队列

链表队列需要维护两个指针：front 指向头节点（出队端），rear 指向尾节点（入队端）。入队时在尾部追加，出队时从头部删除。这样两端操作都是O(1)。

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

typedef struct {
    QNode *front;
    QNode *rear;
} LinkedQueue;

// 入队（尾插）
int enqueue(LinkedQueue *q, int value) {
    QNode *newNode = (QNode *)malloc(sizeof(QNode));
    if (!newNode) return -1;
    newNode->data = value;
    newNode->next = NULL;
    if (q->rear) {
        q->rear->next = newNode;
    } else {
        q->front = newNode;  // 第一个节点
    }
    q->rear = newNode;
    return 0;
}

// 出队（头删）
int dequeue(LinkedQueue *q, int *value) {
    if (!q->front) return -1;
    QNode *temp = q->front;
    *value = temp->data;
    q->front = temp->next;
    if (!q->front) {
        q->rear = NULL;  // 队列变空
    }
    free(temp);
    return 0;
}

数组 vs 链表：怎么选？

我个人习惯这样判断：如果数据量是确定的、对实时性要求高，就用数组；如果数据量变化大、需要灵活伸缩，就用链表。下面这个表格可以帮你快速决策：

对比维度 数组实现 链表实现
内存分配 静态分配，编译期确定 动态分配，运行时申请
空间效率 可能浪费（预留最大空间） 按需分配，但有指针开销
时间效率 O(1)，无动态分配开销 O(1)，但malloc/free有耗时
适用场景 RTOS任务栈、固定大小缓冲 消息队列、动态任务调度
风险点 栈溢出、队列满 内存碎片、分配失败

知识体系总览

下面这张图把栈和队列的核心逻辑串起来了。你可以看到，两种结构都有数组和链表两种实现方式，但操作的本质是一样的——栈只在一端操作，队列在两端操作。

栈与队列知识体系 栈（后进先出） 数组实现 固定大小 top指针操作 无动态开销 链表实现 动态扩展 头插头删 需malloc/free 核心操作 push(入栈) → top++ pop(出栈) → top-- peek(查看栈顶) 只在一端操作 队列（先进先出） 循环数组 front/rear指针 牺牲一格判满 无碎片问题 链表实现 动态扩展 尾插头删 需管理内存 核心操作 enqueue(入队) → 尾插 dequeue(出队) → 头删 front/rear分离 两端各司其职 选择依据：确定场景用数组，灵活场景用链表

避坑指南

最后分享几个我实际项目中踩过的坑，希望能帮你少走弯路：

  • 栈溢出检测不能省：我曾经在一个通信协议栈里忘了做栈满检查，结果数据量一大就把数组写穿了，覆盖了相邻变量的值，查了整整两天才定位到问题。从那以后，我所有栈操作都加了边界判断。
  • 循环队列的"假满"问题：如果你用 front == rear 判断队空，用 (rear+1)%N == front 判断队满，那队列实际能用的元素是 N-1 个。我见过有人忘了这茬，结果队列永远装不满就报满了。
  • 链表队列的尾指针更新：出队时如果队列变空，记得把 rear 也置为 NULL。我犯过这个错——出队最后一个元素后，rear 还指着已经被 free 掉的节点，下次入队时直接写野指针。

栈和队列看似简单，但用好了能解决很多实际问题。我个人建议你先把数组版本的实现写熟练，因为嵌入式里大部分场景用数组就够了。链表版本理解原理即可，真要用的时候再根据内存情况决定。

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

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