8、链式栈的实现

好，咱们今天来聊聊链式栈。说实话，顺序栈和链式栈就像一对兄弟，各有各的脾气。我个人习惯在项目里根据场景选，但不管怎么选，先把链式栈搞明白再说。

8.1 链式栈的节点定义

链式栈，说白了就是用链表实现栈。每个节点里存数据，再加一个指针指向下一个节点。嗯，这里要注意：栈顶在链表头部，这样入栈出栈都是 O(1)。

// 链式栈节点定义
typedef struct StackNode {
    int data;               // 数据域
    struct StackNode *next; // 指针域
} StackNode;

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

我在项目中遇到过一个问题：有人把栈顶放在链表尾部，结果每次出栈都要遍历到末尾，性能直接崩了。你想想看，栈的操作都在一端，干嘛不选头部？

8.2 链式栈的入栈与出栈

入栈操作（push）

入栈其实很简单。新节点指向当前栈顶，然后更新栈顶指针。我刚开始写的时候老忘记更新 size，后来养成了习惯——每次操作完顺手维护一下计数器。

// 入栈
int push(LinkedStack *stack, int value) {
    if (stack == NULL) return -1;
    
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        return -1;
    }
    
    newNode->data = value;
    newNode->next = stack->top;  // 新节点指向当前栈顶
    stack->top = newNode;        // 更新栈顶
    stack->size++;
    
    return 0;
}

出栈操作（pop）

出栈就是把栈顶节点摘下来。注意要保存数据，释放内存。嗯，这里有个坑——栈为空时不能出栈。

// 出栈
int pop(LinkedStack *stack, int *value) {
    if (stack == NULL || stack->top == NULL) {
        printf("栈为空，无法出栈\n");
        return -1;
    }
    
    StackNode *temp = stack->top;
    *value = temp->data;
    stack->top = temp->next;  // 栈顶下移
    free(temp);                // 释放内存
    stack->size--;
    
    return 0;
}

8.3 链式栈的完整实现

把上面这些拼起来，再加个初始化、判空、获取栈顶，就是一个完整的链式栈了。

// 初始化
void initStack(LinkedStack *stack) {
    stack->top = NULL;
    stack->size = 0;
}

// 判空
int isEmpty(LinkedStack *stack) {
    return stack->top == NULL;
}

// 获取栈顶元素
int getTop(LinkedStack *stack, int *value) {
    if (isEmpty(stack)) return -1;
    *value = stack->top->data;
    return 0;
}

// 销毁栈
void destroyStack(LinkedStack *stack) {
    while (stack->top != NULL) {
        StackNode *temp = stack->top;
        stack->top = temp->next;
        free(temp);
    }
    stack->size = 0;
}

8.4 顺序栈与链式栈的对比

说到对比，我直接给你一张表，一目了然。

对比维度	顺序栈	链式栈
存储方式	连续内存（数组）	离散内存（链表节点）
空间效率	固定大小，可能浪费	动态分配，按需使用
时间效率	入栈出栈 O(1)，无额外开销	入栈出栈 O(1)，但有 malloc/free 开销
扩容	需要 realloc，可能搬移数据	无需扩容，随用随分配
内存碎片	无碎片	频繁分配释放会产生碎片
适用场景	数据量可预估，追求极致性能	数据量不确定，需要灵活扩展

为什么会这样？说白了就是顺序栈用数组，链式栈用链表。数组访问快但扩容麻烦，链表灵活但每次操作都要动内存。

8.5 知识体系图

下面这张图把链式栈的核心逻辑串起来了，你一看就明白。

你看，链式栈的核心就三块：节点怎么定义、入栈出栈怎么实现、跟顺序栈比有什么优劣。搞清楚了这些，面试写代码基本没问题。

---

公众号:蓝海资料掘金营，微信deep3321