C++中栈结构建立与操作详细解析

什么是栈？

栈（stack）是一种特殊的数据结构，它只允许在一个端口进行插入和删除操作。这个端口常被称为栈顶（top）。栈的正常操作是先进后出（LIFO），也就是说后进入的元素会先被弹出。

举个例子，假设我们将一叠盘子放在桌子上，每新洗好一个盘子，我们就把它放在盘子栈的顶端。当我们需要取出盘子时，我们从栈顶开始一个一个地弹出，直到取到需要的盘子。

如何在C++中实现栈？

C++中实现栈最常用的方法是使用STL库中的stack。它提供了一系列函数用于实现栈的功能，包括：

• push()：在栈顶插入一个元素
• pop()：弹出并删除栈顶元素
• top()：返回栈顶元素的值
• empty()：检查栈是否为空
• size()：返回栈的大小

stack的定义如下：

#include <stack>

std::stack<int> myStack; // 这行代码定义了一个名为myStack的栈，存储int类型的元素

示例一：使用栈判断括号是否匹配

栈经常用于处理括号匹配问题。我们可以定义一个栈，遇到左括号则将其压入栈顶，遇到右括号则弹出栈顶元素并判断是否与此右括号匹配，若不匹配则括号不匹配。

以括号匹配为例，下面是一个示例程序：

#include <iostream>
#include <stack>

bool isBalanced(std::string str) {
    std::stack<char> myStack; // 定义一个char类型的栈
    for (char c : str) {
        if (c == '{' || c == '[' || c == '(') {
            myStack.push(c); // 左括号压入栈顶
        } else if (c == '}' || c == ']' || c == ')') {
            if (myStack.empty()) {
                return false; // 栈为空时，右括号未匹配
            }
            char top = myStack.top(); // 获取栈顶元素
            myStack.pop(); // 弹出栈顶元素
            if (c == '}' && top != '{') {
                return false; // 不匹配则返回false
            } else if (c == ']' && top != '[') {
                return false;
            } else if (c == ')' && top != '(') {
                return false;
            }
        }
    }
    return myStack.empty(); // 栈为空则括号匹配，否则不匹配
}

int main() {
    std::string str = "{[()]()}"; // 测试字符串
    if (isBalanced(str)) {
        std::cout << "括号匹配" << std::endl;
    } else {
        std::cout << "括号不匹配" << std::endl;
    }
    return 0;
}

在上述代码中，函数isBalanced接收一个字符串作为参数，返回一个布尔值以表示该字符串中的括号是否匹配。函数内部定义了一个char类型的栈myStack，通过遍历字符串str中的每一个字符判断是否为左括号或右括号，并根据左右括号的特性进行匹配判断。最终，如果栈为空，则说明括号匹配，否则不匹配。

示例二：使用栈将中缀表达式转换为后缀表达式

栈还可以用于将中缀表达式转换为后缀表达式。中缀表达式是我们平常使用的表达式形式，例如3 + 4 * 2 / ( 1 - 5 ) ^ 2。而后缀表达式则是将操作数放在前面、操作符放在后面的表达式形式，例如3 4 2 * 1 5 - 2 ^ / +。

将中缀表达式转换为后缀表达式需要使用到栈。我们可以依次遍历中缀表达式中的每个元素：

• 如果是操作数，则直接输出
• 如果是左括号，则入栈
• 如果是右括号，则将栈中元素弹出并输出，直到弹出左括号为止
• 如果是操作符，则判断其优先级与栈顶操作符的优先级，如果更低（或相等）则弹出栈顶元素并输出，直到栈顶操作符的优先级小于该操作符
• 如果遍历完成后栈中还有元素，则依次弹出并输出直到栈为空

下面是将中缀表达式转换为后缀表达式的示例程序：

#include <iostream>
#include <stack>
#include <string>
#include <sstream>

int priority(char op) {
    if (op == '+' || op == '-') {
        return 1;
    } else if (op == '*' || op == '/') {
        return 2;
    } else if (op == '^') {
        return 3;
    }
    return 0;
}

std::string infixToPostfix(std::string str) {
    std::stringstream ss;
    std::stack<char> myStack;

    for (char c : str) {
        if (isdigit(c)) {
            ss << c; // 如果是数字则直接输出
        } else if (c == '(') {
            myStack.push(c); // 如果是左括号则入栈
        } else if (c == ')') {
            while (!myStack.empty() && myStack.top() != '(') {
                ss << myStack.top(); // 弹出栈顶元素并输出，直到弹出左括号为止
                myStack.pop();
            }
            if (!myStack.empty() && myStack.top() == '(') {
                myStack.pop(); // 弹出左括号
            }
        } else {
            while (!myStack.empty() && priority(c) <= priority(myStack.top())) {
                ss << myStack.top(); // 弹出栈顶元素并输出，直到栈顶操作符的优先级小于该操作符
                myStack.pop();
            }
            myStack.push(c); // 将该操作符入栈
        }
    }

    while (!myStack.empty()) {
        ss << myStack.top(); // 如果栈中还有元素，则依次弹出并输出直到栈为空
        myStack.pop();
    }

    return ss.str(); // 返回后缀表达式
}

int main() {
    std::string str = "3+4*2/(1-5)^2"; // 中缀表达式
    std::string postfix = infixToPostfix(str); // 将中缀表达式转换为后缀表达式
    std::cout << postfix << std::endl; // 输出后缀表达式
    return 0;
}

在上述代码中，函数infixToPostfix接收一个字符串作为参数，返回一个字符串表示后缀表达式。函数内部定义了一个char类型的栈myStack，通过遍历输入字符串中的每一个字符，根据其是操作数、左括号、右括号还是操作符进行不同的操作，并输出后缀表达式。最终，返回后缀表达式字符串。