📦 C++ 栈（Stack）通俗易懂教程 🚀

📌 从零掌握栈的定义、实现、操作与励志鼓励语！

🎯 一、什么是栈？

栈（Stack） 是一种 后进先出（LIFO, Last In First Out） 的线性数据结构。

你可以把它想象成：

📦 一个只有一端开口的箱子，只能从顶部放进去或取出来东西。
🔢 最后放进来的元素，最先被取出。

✅ 栈的特点：

  • 后进先出
  • 插入和删除都在栈顶进行
  • 不支持随机访问

🧱 二、栈的基本操作 ⚙️

操作 功能说明
push(x) 将元素 x 压入栈顶
pop() 弹出栈顶元素
top() 获取栈顶元素（不弹出）
empty() 判断栈是否为空
size() 返回栈中元素个数

📈 三、图解栈的操作流程 📊

初始栈：[ ]
push(10) → [10]
push(20) → [10, 20]
push(30) → [10, 20, 30]
top()    → 30
pop()    → [10, 20]

🎯 这就是典型的“先进后出”行为！

🧪 四、C++ 中如何使用栈？💼

在 C++ 中，我们可以用两种方式来实现栈：

  • ✅ 使用 STL 中的 stack 容器适配器
  • ✅ 自定义栈结构（顺序栈/链式栈）

📦 方法一：使用 STL 的 stack（最简单）📦

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s; // 创建一个整型栈

    // 压栈
    s.push(10);
    s.push(20);
    s.push(30);

    cout << "栈顶元素: " << s.top() << endl; // 输出 30

    // 出栈
    s.pop();
    cout << "新的栈顶: " << s.top() << endl; // 输出 20

    // 判断是否为空
    if (s.empty())
        cout << "栈为空！" << endl;
    else
        cout << "栈不为空！" << endl;

    // 获取当前栈大小
    cout << "栈的大小: " << s.size() << endl;

    return 0;
}

📌 输出：

栈顶元素: 30
新的栈顶: 20
栈不为空！
栈的大小: 2

🔗 方法二：自定义顺序栈（使用数组）🔗

适合想了解栈底层原理的同学！

#include <iostream>
#define MAX_SIZE 100
using namespace std;

// 定义顺序栈结构体
typedef struct {
    int data[MAX_SIZE]; // 存储数据
    int top;            // 栈顶指针
} Stack;

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

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

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

// 入栈
bool push(Stack* s, int value) {
    if (isFull(s)) {
        cout << "栈已满，无法压栈！" << endl;
        return false;
    }
    s->data[++s->top] = value;
    return true;
}

// 出栈
bool pop(Stack* s) {
    if (isEmpty(s)) {
        cout << "栈为空，无法出栈！" << endl;
        return false;
    }
    s->top--;
    return true;
}

// 获取栈顶元素
int top(Stack* s) {
    if (isEmpty(s)) {
        cout << "栈为空，无栈顶元素！" << endl;
        return -1;
    }
    return s->data[s->top];
}

// 获取栈大小
int size(Stack* s) {
    return s->top + 1;
}

🧪 主函数测试：

int main() {
    Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    cout << "栈顶元素：" << top(&s) << endl; // 输出 30
    pop(&s);
    cout << "出栈后栈顶：" << top(&s) << endl; // 输出 20

    cout << "栈的大小：" << size(&s) << endl;

    return 0;
}

📌 输出：

栈顶元素：30
出栈后栈顶：20
栈的大小：2

🧠 五、应用场景举例 💡

场景 示例
括号匹配 判断表达式中的括号是否正确闭合
表达式求值 计算中缀、后缀表达式
浏览器历史记录 实现“返回上一页”功能
DFS 深度优先搜索 图或树的遍历
函数调用栈 程序运行时函数的调用机制

📌 六、注意事项 ❗

注意项 说明
下标从 -1 开始 top == -1 表示空栈
避免越界 压栈前要判断栈是否已满
出栈前检查 避免对空栈执行 pop
可读性优化 封装为函数或类更清晰（本篇用结构体）

🎁 七、小彩蛋：递归与栈的关系 🎲

🤔 你知道吗？递归的本质其实就是系统自动维护了一个“函数调用栈”！

每次进入一个函数，它就被压入栈； 每次返回结果，它就从栈中弹出。

🧠 所以你写的每一段递归代码，其实背后都是一段“隐式的栈”在帮你工作！

🏆 八、加油鼓励语 💪

👋 亲爱的同学，你已经掌握了 C++ 中非常实用的栈知识！这是通往算法高手之路的重要一步！

🧩 栈不仅是一个基础的数据结构，更是理解程序运行机制的关键。
🚀 掌握它，你会发现自己能轻松应对很多看似复杂的编程挑战！

🎯 不管是括号匹配、表达式计算，还是深度优先搜索，栈都是你的好帮手！

👏 继续努力，坚持练习，你一定能在编程世界中大放异彩！我们在这里为你打call！👏👏👏

📅 最后更新时间：2025年5月22日 23:07

🎉 祝你学习愉快，早日成为编程高手！🌟

1 条评论

  • @ 2025-5-22 23:12:04

    📚 C++栈(Stack)完全教程：从入门到精通

    🌟 欢迎进入栈的奇妙世界

    在编程的世界里，栈(Stack)是一种非常重要且基础的数据结构。它遵循"后进先出"(Last In First Out, LIFO)的原则，如同叠放的盘子，最后放上去的总是最先被拿走。栈在计算机科学中有着广泛的应用，从函数调用、表达式计算到浏览器的后退功能，都离不开栈的身影。

    今天，我们就来系统学习C++中的栈，从基本概念到实际应用，一步一步揭开栈的神秘面纱！

    🧩 什么是栈？

    栈是一种线性数据结构，它的操作遵循**后进先出(LIFO)**的原则。栈支持两种基本操作：

    • 入栈(Push)：将元素添加到栈顶
    • 出栈(Pop)：从栈顶移除元素

    此外，栈通常还提供以下操作：

    • 查看栈顶元素(Top/Peek)：返回栈顶元素的值，但不移除它
    • 判断栈是否为空(Empty)：检查栈中是否有元素
    • 获取栈的大小(Size)：返回栈中元素的数量

    🌰 生活中的栈比喻

    栈就像一摞盘子：

    • 新盘子总是放在最上面(入栈)
    • 取盘子时总是从最上面拿(出栈)
    • 只能看到最上面的盘子(查看栈顶元素)
    • 如果没有盘子，栈为空(判断栈是否为空)
    • 盘子的总数就是栈的大小(获取栈的大小)

    🔧 栈的基本操作

    栈的核心操作包括：

    1. Push(x)：将元素x压入栈顶
    2. Pop()：移除并返回栈顶元素
    3. Top()：返回栈顶元素，但不移除
    4. Empty()：判断栈是否为空
    5. Size()：返回栈的大小

    这些操作的时间复杂度都是O(1)，即常数时间。

    🛠️ C++中栈的实现方式

    在C++中，栈有多种实现方式：

    1. 使用数组实现栈

    下面是一个使用数组实现的栈：

    #include <iostream>
using namespace std;

const int MAX_SIZE = 100;

template<typename T>
class ArrayStack {
private:
    T data[MAX_SIZE];  // 存储栈中元素的数组
    int top;           // 栈顶指针，指向栈顶元素的下一个位置
    
public:
    // 构造函数
    ArrayStack() {
        top = 0;  // 初始化栈顶指针为0
    }
    
    // 判断栈是否为空
    bool empty() const {
        return top == 0;
    }
    
    // 获取栈的大小
    int size() const {
        return top;
    }
    
    // 入栈操作
    void push(const T& value) {
        if (top >= MAX_SIZE) {
            cout << "栈已满，无法入栈！" << endl;
            return;
        }
        data[top++] = value;
    }
    
    // 出栈操作
    void pop() {
        if (empty()) {
            cout << "栈为空，无法出栈！" << endl;
            return;
        }
        top--;
    }
    
    // 获取栈顶元素
    T topElement() const {
        if (empty()) {
            cout << "栈为空，没有栈顶元素！" << endl;
            return T();  // 返回默认值
        }
        return data[top - 1];
    }
};

int main() {
    ArrayStack<int> stack;
    
    // 入栈操作
    stack.push(10);
    stack.push(20);
    stack.push(30);
    
    // 输出栈顶元素
    cout << "栈顶元素: " << stack.topElement() << endl;  // 输出: 30
    
    // 出栈操作
    stack.pop();
    cout << "出栈后栈顶元素: " << stack.topElement() << endl;  // 输出: 20
    
    // 输出栈的大小
    cout << "栈的大小: " << stack.size() << endl;  // 输出: 2
    
    return 0;
}

    2. 使用链表实现栈

    下面是一个使用链表实现的栈：

    #include <iostream>
using namespace std;

template<typename T>
struct Node {
    T data;
    Node* next;
    
    Node(const T& value) : data(value), next(nullptr) {}
};

template<typename T>
class LinkedStack {
private:
    Node<T>* topNode;  // 栈顶节点指针
    int count;         // 栈中元素个数
    
public:
    // 构造函数
    LinkedStack() : topNode(nullptr), count(0) {}
    
    // 析构函数
    ~LinkedStack() {
        while (!empty()) {
            pop();
        }
    }
    
    // 判断栈是否为空
    bool empty() const {
        return count == 0;
    }
    
    // 获取栈的大小
    int size() const {
        return count;
    }
    
    // 入栈操作
    void push(const T& value) {
        Node<T>* newNode = new Node<T>(value);
        newNode->next = topNode;
        topNode = newNode;
        count++;
    }
    
    // 出栈操作
    void pop() {
        if (empty()) {
            cout << "栈为空，无法出栈！" << endl;
            return;
        }
        Node<T>* temp = topNode;
        topNode = topNode->next;
        delete temp;
        count--;
    }
    
    // 获取栈顶元素
    T topElement() const {
        if (empty()) {
            cout << "栈为空，没有栈顶元素！" << endl;
            return T();  // 返回默认值
        }
        return topNode->data;
    }
};

int main() {
    LinkedStack<int> stack;
    
    // 入栈操作
    stack.push(10);
    stack.push(20);
    stack.push(30);
    
    // 输出栈顶元素
    cout << "栈顶元素: " << stack.topElement() << endl;  // 输出: 30
    
    // 出栈操作
    stack.pop();
    cout << "出栈后栈顶元素: " << stack.topElement() << endl;  // 输出: 20
    
    // 输出栈的大小
    cout << "栈的大小: " << stack.size() << endl;  // 输出: 2
    
    return 0;
}

    3. 使用C++标准库中的stack容器

    C++标准库提供了stack容器，它是一个适配器类，默认使用deque作为底层容器。

    #include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> stack;
    
    // 入栈操作
    stack.push(10);
    stack.push(20);
    stack.push(30);
    
    // 输出栈顶元素
    cout << "栈顶元素: " << stack.top() << endl;  // 输出: 30
    
    // 出栈操作
    stack.pop();
    cout << "出栈后栈顶元素: " << stack.top() << endl;  // 输出: 20
    
    // 输出栈的大小
    cout << "栈的大小: " << stack.size() << endl;  // 输出: 2
    
    // 判断栈是否为空
    if (stack.empty()) {
        cout << "栈为空" << endl;
    } else {
        cout << "栈不为空" << endl;
    }
    
    return 0;
}

    📊 数组栈 vs 链表栈 vs 标准库栈

    特性 数组栈 链表栈 标准库栈(stack)
    实现方式 静态数组 动态链表 适配器(默认deque)
    内存管理 需要预先分配固定大小 动态分配，按需扩展 自动管理
    插入/删除效率 O(1)
    空间利用率 可能有空间浪费 按需分配，无浪费 自动优化
    适用场景 元素数量固定或已知上限 元素数量不确定 快速开发，无需自定义

    💡 栈的应用场景

    栈在计算机科学中有广泛的应用，常见场景包括：

    1. 函数调用栈

    • 每当调用一个函数时，系统会将当前的执行上下文(局部变量、返回地址等)压入栈中
    • 函数返回时，系统从栈中弹出执行上下文，恢复之前的执行状态
    • 这就是为什么递归过深会导致栈溢出的原因

    2. 表达式求值

    • 中缀表达式转后缀表达式(逆波兰表达式)
    • 后缀表达式的计算
    • 括号匹配检查

    3. 浏览器后退功能

    • 浏览器将用户访问的每个页面依次压入栈中
    • 用户点击后退按钮时，从栈中弹出页面并显示

    4. 编辑器的撤销操作

    • 编辑器将用户的每一步操作压入栈中
    • 用户点击撤销按钮时，从栈中弹出最近的操作并恢复

    🚀 栈的经典问题

    1. 括号匹配问题

    问题描述：检查表达式中的括号是否匹配

    解决思路：

    • 遍历表达式，遇到左括号时入栈
    • 遇到右括号时，弹出栈顶元素并检查是否匹配
    • 遍历结束后，栈应为空
    #include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isMatchingPair(char left, char right) {
    if (left == '(' && right == ')') return true;
    if (left == '[' && right == ']') return true;
    if (left == '{' && right == '}') return true;
    return false;
}

bool isBalanced(string expr) {
    stack<char> s;
    
    for (char c : expr) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);  // 左括号入栈
        } else if (c == ')' || c == ']' || c == '}') {
            if (s.empty()) {
                return false;  // 右括号多余
            }
            char top = s.top();
            s.pop();
            if (!isMatchingPair(top, c)) {
                return false;  // 括号不匹配
            }
        }
    }
    
    return s.empty();  // 栈为空表示括号完全匹配
}

int main() {
    string expr = "{[()]}";
    if (isBalanced(expr)) {
        cout << "括号匹配" << endl;
    } else {
        cout << "括号不匹配" << endl;
    }
    
    return 0;
}

    2. 逆波兰表达式求值

    问题描述：计算逆波兰表达式(后缀表达式)的值

    解决思路：

    • 遍历表达式，遇到操作数时入栈
    • 遇到运算符时，弹出栈顶的两个操作数进行计算，并将结果入栈
    • 遍历结束后，栈顶元素即为表达式的值
    #include <iostream>
#include <stack>
#include <string>
#include <sstream>
using namespace std;

int evaluateRPN(vector<string>& tokens) {
    stack<int> s;
    
    for (string token : tokens) {
        if (token == "+" || token == "-" || token == "*" || token == "/") {
            // 遇到运算符，弹出两个操作数
            int b = s.top(); s.pop();
            int a = s.top(); s.pop();
            
            // 计算结果并压入栈
            if (token == "+") s.push(a + b);
            else if (token == "-") s.push(a - b);
            else if (token == "*") s.push(a * b);
            else if (token == "/") s.push(a / b);
        } else {
            // 遇到操作数，转换为整数并入栈
            int num;
            stringstream ss(token);
            ss >> num;
            s.push(num);
        }
    }
    
    return s.top();  // 返回栈顶元素
}

int main() {
    vector<string> tokens = {"2", "1", "+", "3", "*"};
    int result = evaluateRPN(tokens);
    cout << "表达式的值: " << result << endl;  // 输出: 9
    
    return 0;
}

    🌟 总结与鼓励

    恭喜你完成了C++栈的学习！现在你已经掌握了：

    1. 栈的基本概念和后进先出(LIFO)的原则
    2. 栈的基本操作：入栈、出栈、查看栈顶元素、判断栈是否为空、获取栈的大小
    3. 栈的三种实现方式：数组栈、链表栈和C++标准库中的stack容器
    4. 栈的应用场景和经典问题：函数调用栈、表达式求值、括号匹配等

    栈是编程中非常重要的一种数据结构，希望你能够熟练掌握并灵活运用。继续加油，你一定能在编程的道路上越走越远！ 💪

    📚 拓展学习

    • 练习更多栈相关的算法题（如迷宫求解、汉诺塔等）
    • 学习栈与递归的关系
    • 探索栈在编译器、操作系统等领域的应用
    • 研究其他数据结构（如队列、链表、树等）

    记住，编程的进步源于不断的实践和思考。继续加油，你一定能成为编程高手！ 🚀

    • 1
    428
    已通过
    0
    题解被赞
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. 版权申诉
    6. Language
    7. 兼容模式
    8. 主题
    4. 在线咨询
    5. Worker 0, 20ms
    6. Powered by Hydro v4.13.3 Community