【C++篇】从装书到抽书：用C++模拟实现“栈”的妙趣演绎

熬夜学编程的小王

发布于 2024-11-25 14:29:22

4080

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！ 👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！ 🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

1 C++stack前言与背景

1.1 前言

在日常生活中，我们经常会接触到一些具有“后进先出”特性的场景，例如堆叠书本、餐具摞放、撤销操作等。这些行为背后都暗含着栈（Stack）这一经典的数据结构概念。在程序设计中，栈以其操作简单、逻辑清晰的特点，广泛应用于表达式求值、括号匹配、递归调用等问题。

C++ 提供了强大的标准模板库（STL），其中 std::stack 是对栈的直接封装。然而，学习如何手动实现一个栈可以帮助我们理解其工作原理，同时提升我们的逻辑能力和代码实现能力。本篇博客将从栈的背景出发，深入探讨其原理，并以手动实现为切入点，带领读者领略栈的核心魅力。

1.2 背景

栈通常有两种常见的实现方式：

基于数组的实现： 使用固定大小的数组存储栈元素，简单高效，但需要提前确定容量，可能导致浪费或溢出。
基于链表的实现： 使用动态链表存储栈元素，支持动态扩展，但实现和管理相对复杂。

栈的应用场景

栈以其独特的操作方式，被广泛应用于许多程序设计问题中，以下是一些经典场景：

表达式求值： 使用后缀表达式（逆波兰表达式）进行高效计算。
括号匹配： 验证字符串中括号是否成对出现并正确嵌套。
递归实现： 通过函数调用栈实现递归算法。
撤销操作： 用于文本编辑器等工具中保存历史操作。

在 C++ 中，栈（stack）是一个非常常用的数据结构，它以**后进先出（LIFO, Last In First Out）**的方式进行操作。虽然 STL 提供了现成的 std::stack，但学习如何手动实现一个栈不仅能帮助我们理解其底层原理，还能提升代码能力。本文将从栈的原理、手动实现及其实际应用三个方面来讲解。

2. 深入理解 C++ 中的 Stack 模拟及应用

2.1 栈的基本原理

栈是一种受限访问的线性数据结构，仅允许：

入栈（Push）： 将元素压入栈顶。
出栈（Pop）： 移除栈顶元素。
访问栈顶元素（Top/Peek）： 查看当前栈顶的值。
检查栈是否为空（IsEmpty）： 确认栈的状态。

常见的实现方式有两种：

基于数组（固定大小）
基于链表（动态大小）

2.2 用数组模拟栈

代码实现

#include <iostream>
#include <stdexcept> // 用于抛出异常
using namespace std;

class Stack {
private:
    int* arr;       // 数组指针
    int capacity;   // 栈容量
    int topIndex;   // 栈顶索引
public:
    // 构造函数：初始化栈
    Stack(int size) {
        if (size <= 0) throw invalid_argument("Stack size must be positive.");
        capacity = size;
        arr = new int[capacity];
        topIndex = -1; // 栈为空时，topIndex 为 -1
    }

    // 析构函数：释放内存
    ~Stack() {
        delete[] arr;
    }

    // 入栈操作
    void push(int value) {
        if (topIndex == capacity - 1) {
            throw overflow_error("Stack overflow: Cannot push to a full stack.");
        }
        arr[++topIndex] = value; // 先自增索引再赋值
    }

    // 出栈操作
    void pop() {
        if (isEmpty()) {
            throw underflow_error("Stack underflow: Cannot pop from an empty stack.");
        }
        --topIndex; // 索引回退即可，实际值无需清除
    }

    // 查看栈顶元素
    int top() const {
        if (isEmpty()) {
            throw underflow_error("Stack is empty: No top element.");
        }
        return arr[topIndex];
    }

    // 检查栈是否为空
    bool isEmpty() const {
        return topIndex == -1;
    }

    // 获取当前栈的大小
    int size() const {
        return topIndex + 1;
    }
};

int main() {
    try {
        Stack s(5);
        s.push(10);
        s.push(20);
        cout << "栈顶元素: " << s.top() << endl;
        s.pop();
        cout << "出栈后栈顶: " << s.top() << endl;
        cout << "栈是否为空: " << (s.isEmpty() ? "是" : "否") << endl;
    } catch (exception& e) {
        cerr << e.what() << endl;
    }
    return 0;
}

特点

数组实现简单且操作高效，但大小固定，容易出现栈溢出。

2.3 用链表模拟栈

代码实现

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

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class Stack {
private:
    Node* topNode; // 指向栈顶的指针
    int currentSize;
public:
    Stack() : topNode(nullptr), currentSize(0) {}

    ~Stack() {
        while (!isEmpty()) {
            pop(); // 遍历链表逐一释放
        }
    }

    // 入栈操作
    void push(int value) {
        Node* newNode = new Node(value);
        newNode->next = topNode;
        topNode = newNode;
        ++currentSize;
    }

    // 出栈操作
    void pop() {
        if (isEmpty()) {
            throw underflow_error("Stack underflow: Cannot pop from an empty stack.");
        }
        Node* temp = topNode;
        topNode = topNode->next;
        delete temp;
        --currentSize;
    }

    // 查看栈顶元素
    int top() const {
        if (isEmpty()) {
            throw underflow_error("Stack is empty: No top element.");
        }
        return topNode->data;
    }

    // 检查栈是否为空
    bool isEmpty() const {
        return topNode == nullptr;
    }

    // 获取当前栈的大小
    int size() const {
        return currentSize;
    }
};

int main() {
    try {
        Stack s;
        s.push(5);
        s.push(15);
        cout << "栈顶元素: " << s.top() << endl;
        s.pop();
        cout << "出栈后栈顶: " << s.top() << endl;
        cout << "栈大小: " << s.size() << endl;
    } catch (exception& e) {
        cerr << e.what() << endl;
    }
    return 0;
}

特点

链表实现支持动态大小，灵活性更高，但需要额外的内存管理。

3.栈的实际应用

3.1 括号匹配

栈常用于检查字符串中的括号是否匹配，如 ({[]}) 是合法的，而 ({[}) 则不合法。

题目链接：20. 有效的括号 - 力扣（LeetCode）

示例代码

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

bool isValid(const string& str) {
    stack<char> s;
    for (char c : str) {
        if (c == '(' || c == '{' || c == '[') {
            s.push(c);
        } else {
            if (s.empty()) return false;
            char top = s.top();
            if ((c == ')' && top == '(') || 
                (c == '}' && top == '{') || 
                (c == ']' && top == '[')) {
                s.pop();
            } else {
                return false;
            }
        }
    }
    return s.empty();
}

int main() {
    string input = "{[()]}";
    cout << (isValid(input) ? "匹配" : "不匹配") << endl;
    return 0;
}

3.2 计算表达式（逆波兰表达式求值）

题目链接：150. 逆波兰表达式求值 - 力扣（LeetCode）

后缀表达式（逆波兰表达式）计算可以用栈高效实现。

示例代码：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;//入栈是整数
        for(auto ch:tokens)
        {
            if(ch=="+"||ch=="-"||ch=="*"||ch=="/")
            {
                int right=st.top();//获取右操作数
                st.pop();
                int left=st.top();//获取左操作数
                st.pop();
                if(ch=="+")
                    st.push(left+right);//将计算后的表达式再入栈，以供接下来其它数字的使用
                else if(ch=="-")
                    st.push(left-right);
                else if(ch=="*")
                    st.push(left*right);
                else if(ch=="/")
                    st.push(left/right);
            }
            else{
                st.push(stoi(ch));//将字符串转化为整数，再入栈
            }
        }
        return st.top();//返回计算表达式的结果
    }
};

4.总结

栈是一种简单但功能强大的数据结构。通过本文的学习，你不仅了解了栈的基本原理，还掌握了用数组和链表实现栈的能力，以及栈在实际中的应用。手动实现栈虽然较繁琐，但能够深入理解其工作机制，为编写高效代码奠定扎实的基础。

5. 结语

通过实现栈的模拟，我们不仅收获了一段代码，更收获了一种面对问题的解决思路。希望这篇分享能够启发你，在数据结构的学习和应用之路上不断前行。正如编程所教会我们的那样：一步一步构建，一个一个解决，最终抵达成功的顶峰。

如果你有更好的优化想法或应用场景，欢迎交流讨论，一起探索 C++ 的更多可能性！

下一篇文章再会！！！

路虽远，行则将至；事虽难，做则必成

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-11-24，如有侵权请联系 cloudcommunity@tencent.com 删除

c++