栈：后进先出的艺术

说实话，栈这个概念，我第一次接触时觉得挺简单的。不就是个后进先出吗？但真正在项目里用起来，才发现这里面门道不少。今天我就带你好好捋一捋栈的方方面面。

栈的定义

栈（Stack），说白了就是一种操作受限的线性表。它只允许在一端进行插入和删除操作，这一端我们叫它栈顶，另一端叫栈底。

你想想看，这像什么？就像一摞盘子。你每次只能从最上面拿盘子，也只能把新盘子放在最上面。这就是典型的后进先出（LIFO, Last In First Out）。

我在项目中遇到过一个问题：函数调用时，局部变量的生命周期管理。其实底层就是靠栈来实现的。每次调用函数，就把局部变量压入栈；函数返回时，自动弹出。嗯，这就是栈最经典的应用场景。

栈的顺序存储结构

顺序存储，就是用数组来实现栈。我习惯用一个整型变量 top 来指示栈顶位置。空栈时 top = -1，每入栈一个元素，top 就加 1。

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int top;  // 栈顶指针
} SeqStack;

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

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

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

栈的链式存储结构

链式存储，说白了就是用链表来实现栈。它的好处是：理论上没有大小限制，只要内存够，随便压。

链栈的栈顶就是链表的头结点。入栈就是在头部插入，出栈就是删除头部节点。时间复杂度都是 O(1)，非常高效。

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

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

// 入栈
void Push(LinkStack *s, int x) {
    StackNode *node = (StackNode *)malloc(sizeof(StackNode));
    node->data = x;
    node->next = s->top;
    s->top = node;
    s->count++;
}

// 出栈
int Pop(LinkStack *s, int *x) {
    if (s->top == NULL) {
        return 0;  // 栈空
    }
    StackNode *temp = s->top;
    *x = temp->data;
    s->top = temp->next;
    free(temp);
    s->count--;
    return 1;
}

两栈共享空间

这个技巧挺有意思的。当你有两个栈，而且它们的数据类型相同时，可以让它们共享一个数组。一个栈从数组左端向右生长，另一个从右端向左生长。

为什么会这样设计？你想想看，如果两个栈各自用独立的数组，很容易出现一个栈满了、另一个栈还有很多空位的情况。共享空间就能充分利用内存。

typedef struct {
    int data[MAXSIZE];
    int top1;  // 栈1的栈顶
    int top2;  // 栈2的栈顶
} DoubleStack;

// 初始化
void InitDoubleStack(DoubleStack *s) {
    s->top1 = -1;
    s->top2 = MAXSIZE;
}

// 入栈（flag=1表示栈1，flag=2表示栈2）
int Push(DoubleStack *s, int x, int flag) {
    if (s->top1 + 1 == s->top2) {
        return 0;  // 栈满
    }
    if (flag == 1) {
        s->data[++s->top1] = x;
    } else {
        s->data[--s->top2] = x;
    }
    return 1;
}

我曾经在一个编译器项目中用过这个技巧。当时需要同时处理表达式求值和括号匹配，两个栈的数据类型一样，而且总数据量有上限。用两栈共享空间，内存利用率直接翻倍。嗯，这个设计确实漂亮。

知识体系总览

下面这张图，我把栈的核心知识点串起来了。你可以对照着看，心里有个谱。

这张图把栈的核心脉络理清楚了。从定义出发，分支出两种存储方式，最后引出两栈共享空间这个优化技巧。你对照着看，应该能对栈有个整体把握。

好了，栈的内容就聊到这儿。你把这些代码自己敲一遍，跑一跑，感受一下入栈出栈的过程。代码这东西，光看是学不会的，得动手。