第二十三讲：栈与队列——顺序存储与链式存储

栈和队列，这两个数据结构，说白了就是操作受限的线性表。我刚开始学的时候觉得它们很“傻”——不就是数组和链表加了些规矩吗？后来做嵌入式项目才发现，正是这些“规矩”，让代码变得异常稳定和高效。

今天咱们就把栈和队列彻底讲透。从顺序存储到链式存储，再到实际应用，我会把我在项目中踩过的坑、积累的经验都抖出来。

一、栈：后进先出的艺术

栈的特点就四个字：后进先出（LIFO）。你想想看，往一个桶里放盘子，最后放进去的总是最先被拿出来。这就是栈的直观模型。

1. 顺序栈（数组实现）

顺序栈用数组来存数据，用一个整型变量 top 来标记栈顶位置。我个人习惯把 top 初始化为 -1，表示空栈。为什么？因为这样 top 指向的就是当前栈顶元素的下标，逻辑上很顺。

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

2. 链式栈（链表实现）

顺序栈有个硬伤：大小固定。你想想看，如果 MAX_SIZE 设大了，内存浪费；设小了，又可能溢出。链式栈就没有这个问题，它用链表来存数据，理论上只受堆内存限制。

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

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

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

// 出栈
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;
}

二、队列：先进先出的哲学

队列和栈正好相反：先进先出（FIFO）。就像排队买奶茶，先来的人先买到。这个模型在计算机里太常见了——任务调度、消息队列、缓冲区管理，到处都是它的影子。

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

普通顺序队列有个严重问题：假溢出。队尾指针到了数组末尾，但队头前面还有空位。怎么办？循环队列。把数组首尾相连，形成一个环。

#define QUEUE_SIZE 100

typedef struct {
    int data[QUEUE_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) % QUEUE_SIZE == q->front;
}

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

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

2. 链式队列

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

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

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

// 入队（尾插法）
int enqueue(LinkedQueue *q, int value) {
    QNode *node = (QNode *)malloc(sizeof(QNode));
    if (!node) return -1;
    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++;
    return 0;
}

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

三、栈与队列的实际应用场景

光讲理论没意思。我来说说我在实际项目中是怎么用它们的。

1. 栈的应用

• 函数调用栈：每个函数调用时，局部变量、返回地址都被压入栈。函数返回时弹出。这是 CPU 硬件就支持的东西。
• 表达式求值：比如计算器里的中缀转后缀，再用栈求值。我在一个手持设备上做过这个，用顺序栈，深度设了 20，够用。
• 括号匹配：编译器检查你的代码括号是否成对。遇到左括号入栈，遇到右括号出栈匹配。不匹配就报错。
• 撤销操作：Ctrl+Z 的实现。每次操作压栈，撤销时出栈恢复状态。

2. 队列的应用

• 消息队列：我在一个物联网网关项目里，用循环队列做串口数据缓冲区。MCU 收到一帧数据就入队，主循环里出队解析。这样收发互不干扰。
• 任务调度：RTOS 里的就绪队列，所有就绪任务排成一队，调度器按优先级或时间片从队头取任务执行。
• 广度优先搜索：BFS 算法用队列来保存待访问的节点。比如走迷宫，从起点开始，把相邻节点入队，一层一层往外扩。
• 打印任务队列：多个程序同时请求打印，系统把它们排成队列，一个一个处理。

四、知识体系总览

下面这张图把栈和队列的核心知识点串起来了。你可以把它当作复习提纲。

五、总结与选择建议

好了，栈和队列的核心内容就这些。最后我给出一些实际选择建议：

场景	推荐方案	理由
嵌入式裸机、RTOS	顺序栈 / 循环队列	无动态内存分配，性能稳定，可预测
Linux 应用层	链式栈 / 链式队列	数据量不确定，链表更灵活
高频数据采集	循环队列（2的幂次方大小）	位运算取模，效率极高
深度递归场景	顺序栈（预估最大深度）	避免递归导致的栈溢出

栈和队列是数据结构的基石。理解透了它们，后面学树、图、哈希表都会轻松很多。嗯，今天就到这里，动手写代码吧。

---