0. 前言

我们已经彻底吃透了线性表的全部存储形态：顺序表、单链表、双向循环链表，同时熟练掌握了 STL 排序、去重、二分、最值、计数等全套基础算法。至此，我们拥有了线性存储+基础数据处理的完整底层能力。

从今天开始，我们正式进入受限线性表的学习阶段。所谓受限线性表，就是基于普通线性表，人为限制插入、删除位置，从而拥有更严格、更专一的数据特性。而栈，就是我们接触的第一种受限线性结构。

栈的逻辑极其简单，但算法地位极高、刷题出场率极高、面试问得极深。括号匹配、表达式求值、前缀后缀、单调栈、模拟队列、函数调用、递归回溯、浏览器后退、编辑器撤销，全部基于栈的思想实现。

很多初学者只会背一句话“后进先出”，但完全不懂：栈为什么不能中间增删？数组栈和链表栈各自的优劣？STL stack 底层是顺序表还是链表？为什么栈可以解决括号匹配？栈的时空复杂度为什么极致稳定？

今天我们从零彻底吃透栈的完整体系，包含核心特性、物理结构、两种手写实现、STL 底层剖析、经典模型、复杂度分析、工程场景与面试考点，为后续队列、单调栈、递归进阶打下核心基础。

1. 栈核心理论（必背基石）

1.1 栈的定义

栈是一种仅允许在一端插入、一端删除的受限线性表。

严格规则：

- 只能在栈顶（top）插入数据（入栈 push）

- 只能在栈顶（top）删除数据（出栈 pop）

- 栈底固定不动，不允许中间位置增删、不允许随机访问

1.2 栈核心特性：LIFO

栈的唯一灵魂：LIFO（Last In First Out）后进先出。

最后入栈的元素，最先出栈；最先入栈的元素，最后出栈。

这一条规则，决定了栈所有的算法场景：逆序、匹配、嵌套、回溯。

1.3 栈四大基础操作

所有栈结构，无论数组实现还是链表实现，都只有四个核心接口：

1. push 入栈：栈顶添加元素

2. pop 出栈：删除栈顶元素（不返回值）

3. top 取栈顶：获取栈顶元素数值（不删除）

4. empty 判断空栈：防止空栈操作崩溃

2. 两种物理实现：数组栈 vs 链表栈

栈是逻辑结构，底层可以依托顺序表或链表实现，两种方式各有优劣，面试高频对比考察。

2.1 顺序栈（数组栈）

依托动态数组实现，用变量 top 记录当前栈顶下标。

✅ 优势：内存连续、访问快、缓存命中率高、无指针开销

❌ 劣势：固定容量或需要动态扩容、存在内存冗余

2.2 链式栈（链表栈）

依托单链表实现，永远在链表头部插入删除（对应栈顶操作）。

✅ 优势：动态按需分配、无容量限制、无内存浪费

❌ 劣势：结点指针开销、缓存不友好、访问速度略慢

2.3 工程选型结论（面试满分答案）

日常开发、刷题、STL 底层优先顺序栈；数据量波动极大、不确定上限场景使用链式栈。

3. 手写一：顺序栈（动态数组实现）

模拟 STL stack 底层思路，实现可扩容、边界全覆盖、无内存泄漏的工业级顺序栈。

#include <iostream>
using namespace std;

// 顺序栈（动态扩容）
class ArrayStack
{
private:
    int* data;
    int top;      // 栈顶下标，-1代表空栈
    int capacity; // 栈容量

    // 扩容机制
    void expand()
    {
        int newCap = capacity == 0 ? 4 : capacity * 2;
        int* newData = new int[newCap];
        for(int i = 0; i <= top; i++)
            newData[i] = data[i];
        
        delete[] data;
        data = newData;
        capacity = newCap;
    }

public:
    ArrayStack() : top(-1), capacity(0), data(nullptr) {}

    // 入栈
    void push(int val)
    {
        if(top + 1 >= capacity)
            expand();
        data[++top] = val;
    }

    // 出栈
    void pop()
    {
        if(empty()) return;
        top--;
    }

    // 取栈顶
    int getTop()
    {
        return data[top];
    }

    // 判断空栈
    bool empty()
    {
        return top == -1;
    }

    // 获取元素个数
    int size()
    {
        return top + 1;
    }

    // 析构释放
    ~ArrayStack()
    {
        delete[] data;
    }
};

// 测试
int main()
{
    ArrayStack st;
    st.push(10);
    st.push(20);
    st.push(30);

    while(!st.empty())
    {
        cout << st.getTop() << " ";
        st.pop();
    }
    // 输出：30 20 10
    return 0;
}

4. 手写二：链式栈（单链表实现）

链式栈永远头插、头删，对应栈顶操作，时间复杂度稳定 O(1)。

#include <iostream>
using namespace std;

// 链表结点
struct StackNode
{
    int val;
    StackNode* next;
    StackNode(int v) : val(v), next(nullptr) {}
};

// 链式栈
class LinkStack
{
private:
    StackNode* top; // 栈顶指针

public:
    LinkStack() : top(nullptr) {}

    // 头插入栈
    void push(int val)
    {
        StackNode* newNode = new StackNode(val);
        newNode->next = top;
        top = newNode;
    }

    // 头删出栈
    void pop()
    {
        if(empty()) return;
        StackNode* tmp = top;
        top = top->next;
        delete tmp;
    }

    // 取栈顶
    int getTop()
    {
        return top->val;
    }

    bool empty()
    {
        return top == nullptr;
    }

    // 析构清空
    ~LinkStack()
    {
        while(!empty()) pop();
    }
};

// 测试
int main()
{
    LinkStack st;
    st.push(1);
    st.push(2);
    st.push(3);

    while(!st.empty())
    {
        cout << st.getTop() << " ";
        st.pop();
    }
    // 输出：3 2 1
    return 0;
}

5. STL stack 底层深度剖析

5.1 底层容器（面试必考）

STL stack 默认基于 deque 双端队列实现，是容器适配器，不是独立容器。

可以手动指定底层容器：vector / deque / list 均可适配。

stack<int, vector<int>> st; 基于顺序表栈

stack<int, list<int>> st; 基于链式栈

5.2 为什么默认用 deque？

1. deque 头尾增删 O(1)，完美适配栈顶操作；

2. 分段内存，避免 vector 连续大块内存申请压力；

3. 无频繁扩容拷贝，性能更均衡。

5.3 STL stack 标准接口

stack<int> st;
st.push(10);    // 入栈
st.pop();       // 出栈
st.top();       // 取栈顶
st.empty();     // 判空
st.size();      // 元素个数

重点注意：pop() 无返回值，必须先 top() 取值再 pop()。

6. 栈时间复杂度终极总结

无论顺序栈、链式栈：

- push 入栈：O(1)

- pop 出栈：O(1)

- top 取顶：O(1)

- empty 判空：O(1)

栈是所有数据结构中操作最稳定、速度最快的结构之一。

7. 栈四大经典算法模型（刷题核心）

7.1 逆序输出模型

利用后进先出特性，实现数组、字符串逆序，最简逆序方案。

7.2 括号嵌套匹配模型

左括号入栈，右括号出栈抵消，最终栈空即合法，是栈最经典的嵌套校验模型。

7.3 表达式求值模型

中缀转后缀、后缀求值、运算符优先级匹配，编译器底层逻辑。

7.4 单调栈模型（高阶）

维护栈内单调递增/递减，解决 Next Greater Element、温度趋势、柱状图最大矩形等高频难题，后续专题精讲。

8. 工程真实应用场景

1. 函数调用栈：程序执行、递归深度、栈帧创建销毁

2. 撤销/回退操作：编辑器撤销、浏览器后退

3. 语法解析：括号匹配、表达式解析、编译语法树构建

4. 路径回溯：DFS、深度搜索、状态回溯

9. 高频坑点汇总

1. 空栈取顶、空栈出栈：不判空直接操作，程序崩溃；

2. 混淆栈顶栈底：错误在栈底操作，破坏 LIFO 特性；

3. STL pop 取值错误：试图用 pop() 接收返回值；

4. 顺序栈下标越界：未扩容直接入栈；

5. 链式栈未释放结点：频繁创建导致内存泄漏。

10. 面试满分问答

Q1：栈的核心特性与适用场景？

栈是后进先出的受限线性表，仅支持栈顶增删，适合逆序处理、嵌套匹配、状态回退、函数调用与递归回溯场景。

Q2：顺序栈与链式栈的优劣？

顺序栈速度快、缓存友好、有扩容开销；链式栈无容量限制、动态适配、有指针内存开销。

Q3：STL stack 为什么默认用 deque？

deque 头尾操作 O(1)，无 vector 大块连续内存压力，扩容代价更小，性能更均衡。

Q4：栈所有操作的时间复杂度？

入栈、出栈、取栈顶、判空全部稳定 O(1)，是时间效率极高的数据结构。

11. 全文总结

今天我们完成了栈的完整体系攻坚，从理论特性、LIFO 原理、顺序/链表双实现、STL 底层容器适配器、复杂度分析、刷题模型、工程场景、面试考点全方位吃透。

栈看似简单，却是算法进阶的核心基石。后续的单调栈、队列、递归、深度优先搜索、表达式解析，全部建立在栈的思维之上。