栈与队列：顺序存储与链式存储，以及实际应用场景

大家好，我是老李。今天我们来聊聊数据结构里两个最基础、也最实用的家伙——栈和队列。说实话，我做了十几年嵌入式开发，这两个结构几乎天天见。你想想看，从函数调用到任务调度，从消息处理到数据缓冲，到处都有它们的身影。

栈和队列，说白了就是两种操作受限的线性表。栈是后进先出（LIFO），队列是先进先出（FIFO）。概念很简单，但用好了能解决很多实际问题。我刚开始学的时候也觉得这玩意儿有啥难的？后来在项目中踩过坑，才明白细节决定成败。

一、栈的顺序存储与链式存储

栈的实现方式有两种：顺序栈和链式栈。顺序栈用数组实现，链式栈用链表实现。各有优劣，看场景选。

1. 顺序栈

顺序栈，就是用数组来模拟栈。我们需要一个数组、一个栈顶指针（top）。top指向当前栈顶元素的位置。空栈时top为-1。

#define MAX_SIZE 100

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

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

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

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

嗯，这里要注意。顺序栈的优点是访问速度快，因为数组是连续内存。但缺点也很明显——栈的大小是固定的。我在项目中遇到过这种情况：一个通信协议栈的缓冲区，一开始预估100个元素够用了，结果后来协议升级，数据量翻倍，栈直接溢出了。那叫一个惨啊。

2. 链式栈

链式栈用链表实现，每个节点包含数据和指向下一个节点的指针。栈顶就是链表的头节点。

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

typedef struct {
    StackNode *top;  // 栈顶指针
    int size;        // 栈中元素个数
} LinkedStack;

// 入栈
void push(LinkedStack *s, int value) {
    StackNode *node = (StackNode *)malloc(sizeof(StackNode));
    node->data = value;
    node->next = s->top;
    s->top = node;
    s->size++;
}

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

链式栈的好处是动态扩展，不用担心栈满的问题。但每次入栈出栈都要malloc/free，在嵌入式系统里这可是大忌——频繁的内存分配会导致碎片化。我个人习惯在资源受限的MCU上尽量用顺序栈，除非数据量确实不可预估。

二、队列的顺序存储与链式存储

队列和栈类似，也有顺序和链式两种实现。但队列有个特殊问题——顺序队列的“假溢出”现象。

1. 顺序队列（循环队列）

顺序队列用数组实现，需要两个指针：front（队头）和rear（队尾）。入队时rear后移，出队时front后移。但普通顺序队列有个问题：front前面的空间用不上了，造成假溢出。

解决办法就是循环队列。把数组当成一个环，rear和front在数组末尾时，下一个位置回到数组开头。

#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;
}

循环队列里，判断队满的条件是 (rear+1)%MAX_SIZE == front。这意味着数组里始终有一个空位没用。为什么？因为如果不留这个空位，队满和队空的条件就一样了（front==rear）。

2. 链式队列

链式队列用链表实现，需要两个指针：front指向队头节点，rear指向队尾节点。入队操作在队尾进行，出队操作在队头进行。

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

typedef struct {
    QueueNode *front;  // 队头指针
    QueueNode *rear;   // 队尾指针
    int size;
} LinkedQueue;

// 入队
void enqueue(LinkedQueue *q, int value) {
    QueueNode *node = (QueueNode *)malloc(sizeof(QueueNode));
    node->data = value;
    node->next = NULL;
    
    if (q->rear == NULL) {
        q->front = q->rear = node;
    } else {
        q->rear->next = node;
        q->rear = node;
    }
    q->size++;
}

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

链式队列的好处同样是动态扩展。但要注意，出队时如果队列变空了，一定要把rear也置为NULL。我见过有人只更新front，结果下次入队时rear还指着已经被释放的节点，直接野指针崩溃。

三、栈与队列的对比

特性	顺序栈	链式栈	循环队列	链式队列
存储结构	数组	链表	数组	链表
空间大小	固定	动态	固定	动态
访问速度	快	较慢（malloc开销）	快	较慢（malloc开销）
内存碎片	无	有	无	有
适用场景	大小可预估、性能要求高	大小不可预估	大小可预估、性能要求高	大小不可预估

四、实际应用场景

说了这么多理论，咱们来看看实际中怎么用。我挑几个典型的场景说说。

1. 函数调用栈

这个大家应该都熟悉。每次函数调用，系统会把返回地址、局部变量等信息压入栈中。函数返回时再弹出。这就是栈的经典应用。如果你在调试时看到Call Stack，那就是栈的内容。

2. 表达式求值

编译器里对算术表达式求值，比如"3+4*2"，需要把中缀表达式转成后缀表达式，然后用栈来计算。我记得有一次写一个简易计算器，就是用两个栈实现的——一个操作数栈，一个运算符栈。

3. 消息队列

在嵌入式系统里，任务之间通信经常用消息队列。发送方把消息放入队列尾部，接收方从队列头部取出。这就是典型的先进先出。我在一个物联网项目中，用循环队列实现了传感器数据缓冲，MCU从队列里取数据发送到云端，效果很好。

4. 任务调度

RTOS里的就绪队列，就是按优先级排列的队列。高优先级任务先执行。有些RTOS还支持时间片轮转，每个任务在队列里轮流执行一段时间。

5. 广度优先搜索（BFS）

图算法里，BFS用队列实现。从起点开始，把相邻节点入队，然后依次出队处理。这个在路径规划、网络爬虫里很常见。

五、知识体系总览

下面这张图把栈和队列的知识结构梳理了一下，方便大家理解。

六、总结与建议

栈和队列，说难不难，说简单也不简单。关键是要理解它们的本质——操作受限的线性表。选哪种实现方式，取决于你的应用场景。

我个人建议：

• 在资源受限的嵌入式系统里，优先用顺序存储。性能好，没碎片。
• 如果数据量不可预估，或者需要频繁扩容，用链式存储。
• 循环队列一定要搞清楚队空队满的判断条件，这是最容易出错的地方。
• 链式队列要注意内存管理，malloc/free要配对，避免内存泄漏。

好了，栈和队列就讲到这里。这些东西看着基础，但用好了能解决很多实际问题。下次遇到需要缓冲数据、管理任务、处理嵌套调用的情况，想想能不能用栈或队列来搞定。