栈与队列：如何用数组实现一个栈？

栈这个东西，说白了就是「后进先出」。你想想看，就像一摞盘子，你总是先拿最上面那个。在嵌入式开发里，栈的应用场景太多了——函数调用、中断嵌套、表达式求值，哪哪都离不开它。

我个人习惯用数组来实现栈，原因很简单：在单片机这类资源受限的环境里，动态内存分配有时候不太靠谱。数组实现栈，内存是静态分配的，运行效率也高，心里踏实。

栈的核心结构

一个栈需要三个要素：

• 一块连续的内存空间——就是数组
• 一个栈顶指针——指向当前栈顶元素的位置
• 一个容量上限——防止越界

我在项目中遇到过一个问题：某次调试一个通信协议栈，发现数据总是错乱。查了半天，原来是栈顶指针初始化成了0，但我的代码里判断栈空的条件是 top == -1。嗯，这种细节一旦搞错，排查起来真要命。

代码实现

先看一个最基础的版本。我习惯把栈封装成一个结构体，这样清晰也好维护。

#include <stdio.h>
#include <stdbool.h>

#define STACK_SIZE 100

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

// 初始化栈
void stack_init(Stack *s) {
    s->top = -1;
}

// 判断栈是否为空
bool stack_is_empty(Stack *s) {
    return s->top == -1;
}

// 判断栈是否已满
bool stack_is_full(Stack *s) {
    return s->top == STACK_SIZE - 1;
}

// 入栈
bool stack_push(Stack *s, int value) {
    if (stack_is_full(s)) {
        printf("栈已满，无法入栈\n");
        return false;
    }
    s->data[++s->top] = value;
    return true;
}

// 出栈
bool stack_pop(Stack *s, int *value) {
    if (stack_is_empty(s)) {
        printf("栈已空，无法出栈\n");
        return false;
    }
    *value = s->data[s->top--];
    return true;
}

// 获取栈顶元素（不出栈）
bool stack_peek(Stack *s, int *value) {
    if (stack_is_empty(s)) {
        return false;
    }
    *value = s->data[s->top];
    return true;
}

你看，代码其实不复杂。但有几个地方我得提醒你注意。

栈的典型应用场景

栈这东西，在嵌入式里最常见的用途就是「括号匹配」和「表达式求值」。我举个例子：

假设你要检查一段C代码里的花括号是否成对出现。用栈来做，思路非常直接：遇到左括号就入栈，遇到右括号就出栈。如果最后栈是空的，说明匹配成功。

bool check_braces(const char *code) {
    Stack s;
    stack_init(&s);
    
    for (int i = 0; code[i] != '\0'; i++) {
        if (code[i] == '{') {
            stack_push(&s, '{');
        } else if (code[i] == '}') {
            if (stack_is_empty(&s)) {
                return false;  // 右括号多了
            }
            int tmp;
            stack_pop(&s, &tmp);
        }
    }
    
    return stack_is_empty(&s);
}

我曾经在一个嵌入式脚本解析器里用过这个逻辑。当时有个bug，解析器总是报错，排查了一下午才发现——代码里有个宏定义里的花括号没配对。嗯，从那以后我写代码都会顺手跑一遍括号检查。

数组实现 vs 链表实现

有人可能会问：为什么不用链表实现栈？链表不是更灵活吗？

没错，链表确实灵活，没有容量限制。但在嵌入式环境里，我倾向于用数组，原因有三：

说白了，如果你的栈最大深度是确定的（比如函数调用深度不会超过100层），用数组就对了。我做过一个RTOS的任务栈，每个任务分配固定大小的栈空间，用的就是数组。

#define TASK_STACK_SIZE 256

栈的进阶用法：共享栈

有时候内存特别紧张，两个栈可以共用一个数组。一个从左边往右长，一个从右边往左长。这种叫「共享栈」或「双端栈」。

typedef struct {
    int data[STACK_SIZE];
    int left_top;   // 左栈栈顶
    int right_top;  // 右栈栈顶
} SharedStack;

void shared_init(SharedStack *s) {
    s->left_top = -1;
    s->right_top = STACK_SIZE;
}

bool shared_push_left(SharedStack *s, int value) {
    if (s->left_top + 1 == s->right_top) {
        return false;  // 栈满
    }
    s->data[++s->left_top] = value;
    return true;
}

bool shared_push_right(SharedStack *s, int value) {
    if (s->left_top + 1 == s->right_top) {
        return false;
    }
    s->data[--s->right_top] = value;
    return true;
}

这种设计我在一个内存只有2KB的MCU项目里用过。两个栈分别管理不同的优先级任务，内存利用率高了不少。

栈的核心逻辑图

下面这张图展示了数组实现栈的核心流程，从初始化到入栈出栈，一目了然。