栈与队列：数据结构中的“后进先出”与“先进先出”

说实话，栈和队列这两个东西，是我在嵌入式开发中用得最多的数据结构。你想想看，函数调用、中断处理、消息缓冲……几乎每天都在跟它们打交道。很多初学者觉得它们太简单，不就是“后进先出”和“先进先出”嘛。但我在项目中踩过的坑告诉我——越是基础的东西，越容易出问题。

今天咱们就把栈和队列彻底聊透。从定义到实现，从顺序到链式，再到实际场景。嗯，开始吧。

栈的定义与核心特性

栈，说白了就是一个“后进先出”的容器。你往里面放数据，只能从顶部放；取数据，也只能从顶部取。就像一摞盘子，你最后放上去的，总是最先被拿走。

我个人习惯把栈想象成一个“单向通道”——数据只能从一端进出。这个端叫栈顶，另一端叫栈底。栈底是固定的，栈顶会随着数据进出而移动。

栈的基本操作就三个：

• 入栈（Push）：把数据放到栈顶
• 出栈（Pop）：从栈顶取出数据
• 取栈顶（Top/Peek）：看一眼栈顶是什么，但不取走

顺序栈的实现

顺序栈，就是用数组来实现栈。我最早学栈的时候，用的就是这种方式。简单、直观，但有个问题——数组大小是固定的。

来看代码：

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;  // 栈顶指针，-1表示空栈
} SeqStack;

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

// 判断栈空
int isEmpty(SeqStack *s) {
    return s->top == -1;
}

// 判断栈满
int isFull(SeqStack *s) {
    return s->top == MAX_SIZE - 1;
}

// 入栈
int push(SeqStack *s, int value) {
    if (isFull(s)) {
        return -1;  // 栈满，入栈失败
    }
    s->data[++s->top] = value;
    return 0;
}

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

链栈的实现

链栈，就是用链表来实现栈。它的好处是——没有大小限制。你想想看，嵌入式系统里内存本来就紧张，用顺序栈万一预估不准，要么浪费空间，要么栈溢出。链栈就灵活多了。

链栈的核心思路：把链表的头结点当作栈顶。入栈就是在头部插入，出栈就是在头部删除。

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

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

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

// 判断栈空
int isEmpty(LinkStack *s) {
    return s->top == NULL;
}

// 入栈
int push(LinkStack *s, int value) {
    StackNode *node = (StackNode *)malloc(sizeof(StackNode));
    if (node == NULL) {
        return -1;  // 内存分配失败
    }
    node->data = value;
    node->next = s->top;
    s->top = node;
    return 0;
}

// 出栈
int pop(LinkStack *s, int *value) {
    if (isEmpty(s)) {
        return -1;
    }
    StackNode *temp = s->top;
    *value = temp->data;
    s->top = temp->next;
    free(temp);
    return 0;
}

队列的定义与核心特性

队列，就是“先进先出”。跟栈正好相反。你想想排队买票——先来的人先买到，后来的人排后面。队列的两端分别叫队头和队尾。数据从队尾入队，从队头出队。

队列的基本操作：

• 入队（Enqueue）：从队尾添加数据
• 出队（Dequeue）：从队头移除数据
• 取队头（Front）：看一眼队头是什么

循环队列的实现

顺序队列有个问题——假溢出。什么意思？就是队尾指针到了数组末尾，但队头前面还有空位。你想想看，明明还有空间，却不能再入队了，多浪费。

循环队列就是来解决这个问题的。它把数组首尾相连，形成一个环。队尾指针到了末尾，就绕回开头。

实现循环队列的关键：

• 用两个指针：front（队头）和 rear（队尾）
• 入队时 rear 后移，出队时 front 后移
• 判断队满：(rear + 1) % MAX_SIZE == front
• 判断队空：front == rear

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;  // 队头指针
    int rear;   // 队尾指针
} CircularQueue;

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

// 判断队空
int isEmpty(CircularQueue *q) {
    return q->front == q->rear;
}

// 判断队满
int isFull(CircularQueue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

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

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

链队列的实现

链队列，就是用链表实现队列。跟链栈类似，它没有大小限制。但队列需要操作两端——队头出队，队尾入队。所以我们需要两个指针：front 指向队头，rear 指向队尾。

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

typedef struct {
    QueueNode *front;  // 队头指针
    QueueNode *rear;   // 队尾指针
} LinkQueue;

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

// 判断队空
int isEmpty(LinkQueue *q) {
    return q->front == NULL;
}

// 入队
int enqueue(LinkQueue *q, int value) {
    QueueNode *node = (QueueNode *)malloc(sizeof(QueueNode));
    if (node == NULL) return -1;
    node->data = value;
    node->next = NULL;
    
    if (isEmpty(q)) {
        q->front = q->rear = node;
    } else {
        q->rear->next = node;
        q->rear = node;
    }
    return 0;
}

// 出队
int dequeue(LinkQueue *q, int *value) {
    if (isEmpty(q)) return -1;
    QueueNode *temp = q->front;
    *value = temp->data;
    q->front = temp->next;
    if (q->front == NULL) {
        q->rear = NULL;  // 队列变空，rear也要置空
    }
    free(temp);
    return 0;
}

实际应用场景

栈和队列在嵌入式系统里无处不在。我挑几个典型的说说：

栈的应用

• 函数调用与返回：每次调用函数，返回地址、局部变量都压入栈。函数返回时弹出。这就是为什么递归太深会栈溢出。
• 中断处理：中断发生时，CPU自动把当前状态压栈。中断返回时弹出。我在做ARM Cortex-M开发时，这个机制帮了大忙。
• 表达式求值：编译器中，中缀表达式转后缀表达式，用的就是栈。比如 3+4*5，转成 3 4 5 * +。
• 括号匹配：检查代码中的括号是否成对。遇到左括号入栈，遇到右括号出栈匹配。不匹配就报错。

队列的应用

• 消息队列：任务间通信。一个任务发消息到队列，另一个任务从队列取消息。我在RTOS中经常用这个。
• 数据缓冲：比如串口接收数据。中断服务程序把数据放入队列，主循环从队列取出处理。这样不会丢数据。
• 任务调度：操作系统中的就绪队列。所有就绪的任务排成队列，调度器按顺序执行。
• 广度优先搜索：图算法中，BFS就是用队列实现的。一层一层往外扩展。

知识体系总览

下面这张图，把栈和队列的核心知识点串起来了。你可以对照着看，哪里还不清楚。

这张图把栈和队列的对比关系画得很清楚。左边是栈，右边是队列。上面是定义，中间是实现方式，下面是应用场景。你可以看到，栈和队列虽然操作方式不同，但实现思路是相通的——都可以用顺序结构或链式结构来实现。

我个人建议，初学者先把顺序栈和循环队列搞透。因为它们的实现更简单，逻辑更清晰。等你把这两个吃透了，链栈和链队列自然就懂了。说白了，链式结构就是顺序结构的“动态版本”，核心思想是一样的。

---

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