目录

一、栈的基础概念：什么是栈？

1.1 栈的核心操作定义

1.2 栈的结构示意图

二、栈的实现：数组 vs 链表，哪种更优？

2.1 栈的结构体定义

2.2 栈的核心接口实现

2.2.1 初始化栈（STInit）

2.2.2 销毁栈（STDestroy）

2.2.3 压栈（STPush）

2.2.4 出栈（STPop）

2.2.5 获取栈顶元素（STTop）

2.2.6 判断栈空（STEmpty）

2.2.7 获取栈大小（STSize）

2.3 栈的基础测试（test.c）

三、栈的实战应用：经典问题解析

3.1 应用 1：括号匹配问题（LeetCode 20）

问题描述

解题思路

代码实现（test1.c）

3.2 应用 2：用栈实现队列（LeetCode 232）

问题描述

解题思路

代码实现（test2.cpp）

四、栈的经典面试题：巩固理解

4.1 题目 1：栈的出栈顺序判断

4.2 题目 2：可能的出栈序列判断

五、总结

---

在数据结构的世界里，栈是一种既基础又关键的线性表结构，其 “后进先出” 的特性使其在算法设计、内存管理、表达式求值等场景中有着广泛应用。接下来我将从栈的基本概念入手，逐步深入到栈的实现细节，再通过实战案例巩固应用，最后结合经典面试题加深理解，带你全面掌握栈的核心知识。

一、栈的基础概念：什么是栈？

栈（Stack）是一种特殊的线性表，它只允许在固定的一端进行数据的插入和删除操作 —— 这一端被称为 “栈顶”，另一端则称为 “栈底”。栈的核心特性是后进先出（LIFO，Last In First Out），即最后插入栈的元素，会最先被删除。

1.1 栈的核心操作定义

为了更清晰地理解栈的行为，我们先明确两个最基础的操作：

• 压栈（Push）：也称 “入栈”，是指将数据插入到栈顶的操作，插入后该数据成为新的栈顶元素。
• 出栈（Pop）：是指将栈顶元素从栈中删除的操作，删除后栈顶位置会向下移动（指向原栈顶的前一个元素）。

举个生活中的例子：叠放的盘子就是一个典型的 “栈”—— 我们只能把新盘子放在最上面（压栈），也只能从最上面拿走盘子（出栈），最下面的盘子（栈底）会最后被取出。

1.2 栈的结构示意图

通过示意图可以更直观地理解栈的 “后进先出” 特性：

1. 初始状态：栈为空，栈顶（Top）指向栈底（此时无元素）；
2. 压栈操作：依次插入元素 7、1、8、2，每次插入后栈顶向上移动；
3. 出栈操作：依次删除元素 2、8、1，每次删除后栈顶向下移动，最终只剩下 7（栈底元素）。

// 初始空栈
栈底 → [     ]
        ↑
      Top（空）

// Push(7) → Push(1) → Push(8) → Push(2)（四次压栈后）
栈底 → [7, 1, 8, 2]
                ↑
              Top（栈顶为2）

// Pop() → Pop() → Pop()（三次出栈后）
栈底 → [7]
        ↑
      Top（栈顶为7）

二、栈的实现：数组 vs 链表，哪种更优？

栈的实现有两种常见方式：数组实现和链表实现。但在实际开发中，数组实现更为常用 —— 因为数组在 “尾端操作”（对应栈的栈顶操作）的时间复杂度是 O (1)，且内存连续、缓存命中率更高；而链表实现需要额外存储指针，且栈顶操作（若用单链表，需将表头作为栈顶）的效率虽也为 O (1)，但综合内存开销和访问速度，数组实现更优。

本文将重点讲解支持动态增长的数组实现（静态数组栈固定大小，灵活性差，实际很少使用）。

2.1 栈的结构体定义

首先，我们需要定义栈的结构体，包含三个核心成员：

• a：指向动态数组的指针，用于存储栈的元素；
• top：栈顶指针（本质是数组下标），表示当前栈顶元素的下一个位置（也可定义为 “指向栈顶元素”，需注意初始化和操作逻辑的一致性）；
• capacity：栈的容量，表示当前动态数组能存储的最大元素个数，用于判断是否需要扩容。

在 C 语言中，结构体定义如下（结合头文件 Stack.h 实现）：

// Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

// 栈元素的数据类型（可根据需求修改，如改为char、float等）
typedef int STDataType;

// 栈的结构体定义
typedef struct Stack {
    STDataType* a;      // 动态数组指针
    int top;            // 栈顶下标（top=0表示空栈，top=capacity表示栈满）
    int capacity;       // 栈的容量
} ST;

2.2 栈的核心接口实现

栈的核心接口包括：初始化、销毁、压栈、出栈、获取栈顶元素、判断栈空、获取栈大小。下面逐一实现这些接口（对应源文件 Stack.c）。

2.2.1 初始化栈（STInit）

初始化的目标是将栈设置为 “空状态”：动态数组指针 a 设为 NULL，栈顶 top 设为 0，容量 capacity 设为 0。

// Stack.c
#include "Stack.h"

// 初始化栈
void STInit(ST* pst) {
    assert(pst);  // 断言：确保传入的栈指针非空（避免野指针访问）
    pst->a = NULL;
    pst->top = 0;
    pst->capacity = 0;
}

2.2.2 销毁栈（STDestroy）

栈是动态分配内存的，使用完毕后必须释放内存，避免内存泄漏：释放动态数组 a，并将 a 设为 NULL，top 和 capacity 重置为 0。

// 销毁栈
void STDestroy(ST* pst) {
    assert(pst);
    free(pst->a);    // 释放动态数组内存
    pst->a = NULL;   // 避免野指针
    pst->top = 0;    // 重置栈顶
    pst->capacity = 0;// 重置容量
}

2.2.3 压栈（STPush）

压栈前需先判断栈是否已满（top == capacity）：若满，则进行扩容（初始容量为 4，后续按 2 倍扩容，平衡效率和内存开销）；扩容成功后，将元素插入到栈顶（a[top]），并将 top 加 1。

// 压栈（插入元素到栈顶）
void STPush(ST* pst, STDataType x) {
    assert(pst);
    // 栈满，需要扩容
    if (pst->top == pst->capacity) {
        // 新容量：空栈时设为4，否则设为原容量的2倍
        int newCapacity = (pst->capacity == 0) ? 4 : 2 * pst->capacity;
        // 重新分配内存（realloc：若pst->a为NULL，等价于malloc）
        STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));
        if (tmp == NULL) {  // 内存分配失败
            perror("realloc failed");  // 打印错误信息
            return;
        }
        pst->a = tmp;          // 更新动态数组指针
        pst->capacity = newCapacity;  // 更新容量
    }
    // 插入元素到栈顶，栈顶上移
    pst->a[pst->top] = x;
    pst->top++;
}

2.2.4 出栈（STPop）

出栈的前提是栈非空（否则会出现 “空栈出栈” 的错误），直接将 top 减 1 即可（无需真正删除元素，后续压栈会覆盖旧值）。

// 出栈（删除栈顶元素）
void STPop(ST* pst) {
    assert(pst);
    assert(pst->top > 0);  // 断言：栈非空
    pst->top--;  // 栈顶下移，等价于删除栈顶元素
}

2.2.5 获取栈顶元素（STTop）

获取栈顶元素前需确保栈非空，栈顶元素的下标为 top - 1（因为 top 指向栈顶元素的下一个位置）。

// 获取栈顶元素
STDataType STTop(ST* pst) {
    assert(pst);
    assert(pst->top > 0);  // 断言：栈非空
    return pst->a[pst->top - 1];  // 返回栈顶元素
}

2.2.6 判断栈空（STEmpty）

栈空的条件是 top == 0，返回一个布尔值（true 为空，false 为非空）。

// 判断栈是否为空（空返回true，非空返回false）
bool STEmpty(ST* pst) {
    assert(pst);
    return (pst->top == 0);
}

2.2.7 获取栈大小（STSize）

栈的大小即当前元素个数，top 的值恰好等于元素个数（因为 top 从 0 开始，每压栈一次加 1）。

// 获取栈中有效元素个数
int STSize(ST* pst) {
    assert(pst);
    return pst->top;
}

2.3 栈的基础测试（test.c）

为了验证栈的接口是否正确，我们编写一个简单的测试程序：初始化栈 → 压入 4 个元素（1、2、3、4）→ 打印栈顶元素 → 出栈 → 循环打印剩余元素 → 销毁栈。

// test.c
#include "Stack.h"

int main() {
    ST s;          // 定义栈变量
    STInit(&s);    // 初始化栈

    // 压入4个元素
    STPush(&s, 1);
    STPush(&s, 2);
    STPush(&s, 3);
    STPush(&s, 4);

    printf("当前栈顶元素：%d\n", STTop(&s));  // 输出：4
    STPop(&s);  // 出栈（删除4）

    // 循环打印剩余元素（直到栈空）
    printf("出栈顺序：");
    while (!STEmpty(&s)) {
        printf("%d ", STTop(&s));  // 打印栈顶
        STPop(&s);                 // 出栈
    }  // 输出：3 2 1

    STDestroy(&s);  // 销毁栈
    return 0;
}

运行结果：

当前栈顶元素：4
出栈顺序：3 2 1

结果符合 “后进先出” 特性，说明栈的接口实现正确。

三、栈的实战应用：经典问题解析

栈的 “后进先出” 特性使其在解决特定问题时极具优势，下面我们分析两个经典应用场景：括号匹配问题、用栈实现队列。

3.1 应用 1：括号匹配问题（LeetCode 20）

问题描述

给定一个只包含 '('、')'、'{'、'}'、'['、']' 的字符串，判断字符串是否有效。有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合；
2. 左括号必须以正确的顺序闭合。

解题思路

利用栈的 “后进先出” 特性：

• 遇到左括号（(、{、[），压入栈中；
• 遇到右括号，先判断栈是否为空（空则无匹配的左括号，直接返回 false），再弹出栈顶元素，判断是否与当前右括号匹配（如 ) 需匹配 (）；
• 遍历结束后，若栈为空（所有左括号都匹配成功），则返回 true，否则返回 false。

代码实现（test1.c）

// test1.c：括号匹配问题
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 栈的结构体定义（元素为char类型，存储括号）
typedef struct Stack {
    char arr[10005];  // 静态数组（假设字符串长度不超过10000）
    int top;          // 栈顶下标（-1表示空栈）
} ST;

// 初始化栈（动态分配栈结构体）
void STInit(ST** st) {
    *st = (ST*)malloc(sizeof(ST));
    (*st)->top = -1;  // 空栈时top=-1
}

// 压栈（插入左括号）
void STPush(ST* st, char* s) {
    st->top++;
    st->arr[st->top] = *s;  // 将当前括号压入栈顶
}

// 出栈（弹出栈顶左括号）
char STPop(ST* st) {
    return st->arr[st->top--];
}

// 判断括号是否有效
bool isValid(char* s) {
    ST* st1;
    STInit(&st1);  // 初始化栈

    while (*s != '\0') {  // 遍历字符串
        // 情况1：栈空且遇到右括号 → 无效
        if (st1->top == -1 && (*s == ']' || *s == '}' || *s == ')')) {
            free(st1);
            return false;
        }
        // 情况2：遇到左括号 → 压栈
        if (*s == '(' || *s == '{' || *s == '[') {
            STPush(st1, s);
        } 
        // 情况3：遇到右括号 → 匹配栈顶
        else {
            char left = STPop(st1);  // 弹出栈顶左括号
            // 不匹配 → 无效
            if ((*s == ')' && left != '(') || 
                (*s == ']' && left != '[') || 
                (*s == '}' && left != '{')) {
                free(st1);
                return false;
            }
        }
        s++;  // 遍历下一个字符
    }

    // 遍历结束后，栈空则所有括号匹配成功
    bool ret = (st1->top == -1);
    free(st1);  // 销毁栈
    return ret;
}

// 测试
int main() {
    char s1[] = "()[]{}";
    char s2[] = "([)]";
    printf("s1是否有效：%s\n", isValid(s1) ? "true" : "false");  // true
    printf("s2是否有效：%s\n", isValid(s2) ? "true" : "false");  // false
    return 0;
}

3.2 应用 2：用栈实现队列（LeetCode 232）

问题描述

队列的核心特性是 “先进先出（FIFO）”，而栈是 “后进先出（LIFO）”。要求用两个栈实现队列的以下操作：

• push(x)：将元素 x 推到队列的末尾；
• pop()：从队列的开头移除并返回元素；
• peek()：返回队列开头的元素；
• empty()：判断队列是否为空。

解题思路

利用两个栈的 “互补” 特性：

• 定义两个栈 st1（输入栈）和 st2（输出栈）；
• push(x)：将元素压入 st1（输入栈只负责 “进”）；
• pop()/peek()：若 st2 为空，将 st1 的所有元素弹出并压入 st2（此时 st2 的栈顶就是队列的队头），再从 st2 弹出 / 获取栈顶；
• empty()：若 st1 和 st2 都为空，则队列为空。

代码实现（test2.cpp）

（注：此处用 C++ 实现，利用 STL 中的 stack 容器简化代码，核心逻辑与 C 语言一致）

// test2.cpp：用栈实现队列
#include <stack>
using namespace std;

class MyQueue {
private:
    stack<int> st1;  // 输入栈：用于接收push的元素
    stack<int> st2;  // 输出栈：用于pop/peek的元素

public:
    // 1. 压入队列末尾
    void push(int x) {
        // 先将st2的所有元素移到st1（确保新元素在st1底部，符合队列顺序）
        while (!st2.empty()) {
            st1.push(st2.top());
            st2.pop();
        }
        st1.push(x);  // 新元素压入st1
    }

    // 2. 弹出队列开头元素并返回
    int pop() {
        // 先将st1的所有元素移到st2（st2栈顶即为队列开头）
        while (!st1.empty()) {
            st2.push(st1.top());
            st1.pop();
        }
        int front = st2.top();  // 获取队列开头
        st2.pop();              // 弹出开头元素
        return front;
    }

    // 3. 获取队列开头元素（不弹出）
    int peek() {
        // 逻辑与pop一致，只是不弹出st2的栈顶
        while (!st1.empty()) {
            st2.push(st1.top());
            st1.pop();
        }
        return st2.top();
    }

    // 4. 判断队列是否为空
    bool empty() {
        // 若st1和st2都为空，则队列为空
        while (!st1.empty()) {
            st2.push(st1.top());
            st1.pop();
        }
        return st2.empty();
    }
};

// 测试
int main() {
    MyQueue* obj = new MyQueue();
    obj->push(1);
    obj->push(2);
    printf("队列开头元素：%d\n", obj->peek());  // 输出：1
    printf("弹出的元素：%d\n", obj->pop());    // 输出：1
    printf("队列是否为空：%s\n", obj->empty() ? "true" : "false");  // false
    delete obj;
    return 0;
}

四、栈的经典面试题：巩固理解

除了上述应用，栈的面试题还常涉及基础概念和特性判断，下面整理几道高频题目：

4.1 题目 1：栈的出栈顺序判断

问题：一个栈的初始状态为空，现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）A. 12345ABCDE B. EDCBA54321 C. ABCDE12345 D. 54321EDCBA答案：B解析：栈是 “后进先出”，最后入栈的 E 最先出栈，最先入栈的 1 最后出栈，顺序为 E→D→C→B→A→5→4→3→2→1。

4.2 题目 2：可能的出栈序列判断

问题：若进栈序列为 1、2、3、4，进栈过程中可以出栈，则下列不可能的出栈序列是（ ）A. 1,4,3,2 B. 2,3,4,1 C. 3,1,4,2 D. 3,4,2,1答案：C解析：

• A 可能：1 进→1 出→2、3、4 进→4 出→3 出→2 出；
• B 可能：1、2 进→2 出→3 进→3 出→4 进→4 出→1 出；
• C 不可能：3 进→3 出后，栈内剩余 1、2，下一个出栈的只能是 2，无法是 1；
• D 可能：1、2、3 进→3 出→4 进→4 出→2 出→1 出。

五、总结

栈作为一种 “受限” 的线性表，其 “后进先出” 的特性是核心。本文从概念入手，详细讲解了栈的数组实现（动态增长）、基础接口测试，再通过括号匹配、用栈实现队列两个实战案例加深应用，最后结合面试题巩固理解。

掌握栈的关键在于：

1. 理解 “后进先出” 的特性，明确栈顶和栈底的操作边界；
2. 实现时注意动态扩容的逻辑（避免内存溢出）和内存释放（避免内存泄漏）；
3. 遇到问题时，思考如何利用 “后进先出” 特性简化逻辑（如括号匹配中左括号的暂存、队列实现中输入输出栈的转换）。

栈是后续学习更复杂数据结构（如二叉树遍历、图的深度优先搜索）的基础，希望本文能帮助你扎实掌握栈的核心知识！