栈与队列基础：从结构到实战

栈和队列，这两个概念在数据结构里属于入门级，但说实话，我做了十几年嵌入式开发，几乎每天都在跟它们打交道。任务调度、函数调用、中断处理……底层系统里到处都是它们的影子。今天我们就来彻底搞懂它们。

栈的定义与操作

栈，说白了就是一种“后进先出”的结构。你想想看，就像一摞盘子，你总是先拿最上面那个。放盘子（入栈）和取盘子（出栈）都只能在顶部操作。

我个人习惯把栈想象成一个只有一个口的盒子。你往里面放东西，只能从那个口放；取东西，也只能从那个口取。最后放进去的，反而最先被拿出来。

栈的核心操作其实就几个：

• push：入栈，把元素放到栈顶
• pop：出栈，把栈顶元素移除
• top/peek：看一眼栈顶元素，但不移除
• isEmpty：判断栈是不是空的
• size：获取栈中元素个数

栈的顺序存储

顺序存储，就是用数组来实现栈。这是最直观的方式。我刚开始学数据结构时，第一个手写的栈就是数组版的。

实现思路很简单：用一个数组，再加一个变量记录栈顶位置。入栈时，栈顶指针往上走；出栈时，栈顶指针往下走。

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

顺序栈的优点很明显：实现简单，访问速度快。缺点呢？大小固定，用多少空间得提前想好。我一般用在确定数据量不会太大的场景，比如表达式求值、括号匹配这些。

栈的链式存储

链式存储，就是用链表来实现栈。每个节点包含数据和指向下一个节点的指针。入栈出栈都在链表头部操作。

为什么要用链式栈？说白了，就是不怕栈满。只要内存够，想放多少放多少。我在做动态内存管理的模块时，就特别喜欢用链式栈。

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

链式栈的缺点也很明显：每个节点额外占用一个指针的空间，而且内存分配有开销。但好处是灵活，不用担心栈满的问题。

队列的定义与操作

队列和栈正好相反，它是“先进先出”的结构。就像排队买票，先来的人先买到票。队列有两个口：一个入口（队尾），一个出口（队头）。

队列的核心操作：

• enqueue：入队，从队尾添加元素
• dequeue：出队，从队头移除元素
• front：查看队头元素
• isEmpty：判断队列是否为空

队列的实现也有顺序和链式两种。顺序队列有个经典问题叫“假溢出”——队尾指针到数组末尾了，但队头前面还有空位。解决办法是用循环队列。

#define MAX_QUEUE 100

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

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

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

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

链式队列就更直接了，用链表实现，头指针指向队头，尾指针指向队尾。入队操作在尾部，出队操作在头部。

我在项目中用过队列的地方太多了：串口数据接收、任务调度、按键事件处理……几乎只要有“先来后到”的需求，队列就是首选。

知识体系总览

下面这张图，把栈和队列的核心知识点串起来了。你可以把它当作一个快速索引，复习时扫一眼就能想起来。

栈和队列，一个后进先出，一个先进先出。看似简单，但它们是很多复杂算法和系统设计的基础。我个人觉得，理解这两个结构的关键不在于记住代码，而在于理解它们的“规则”——什么时候该用栈，什么时候该用队列，这比背代码重要得多。