C++中Stack(栈)的使用方法与基本操作详解

Stack是什么？

Stack（栈）是一种先进后出（Last In First Out）的线性数据结构，即最后被压入的元素会首先被弹出。栈的主要操作有“进栈”（push）和“出栈”（pop），以及“查看栈顶元素”（top）。

在C++中，我们可以使用STL(Standard Template Library)提供的stack容器来实现栈结构。

Stack的基本操作详解

初始化Stack

在使用Stack之前，需要先创建一个Stack对象来存储数据。STL提供了默认初始化的语法：

#include <stack>
using namespace std;

stack<int> st; // 创建空栈

上面的代码创建了一个空的Stack对象st，其中<int>表示存储的元素类型为整数。

进栈

将元素插入到栈的顶部需要使用push函数，例如：将3, 5, 7依次进栈，可以这样写：

st.push(3);
st.push(5);
st.push(7);

查看栈顶元素

使用top()函数可以查看栈顶元素，注意：使用top()前需确保栈不为空，否则会出现运行时错误。

if(!st.empty()){
    cout<<st.top()<<endl; //输出7
}

出栈

从栈中弹出元素需要使用pop()函数。例如：

st.pop(); //弹出栈顶元素7

判断栈是否为空

使用empty()函数可以判断栈是否为空，它返回一个bool值。例如：

if(!st.empty()){
    cout<<"栈不为空"<<endl;
}

获取栈的大小

使用size()函数获取栈的大小，它返回一个unsigned int类型。例如：

size_t size = st.size();
cout<<"栈的大小是："<<size<<endl;

Stack的应用示例

例子一：括号匹配

使用栈判断表达式中的括号是否匹配，我们可以将左括号入栈，右括号时出栈比较：

bool isMatch(string s){
    stack<char> st;
    for(char c: s){
        if(c == '(' || c == '{' || c == '['){
            st.push(c);
        }
        else{
            if(st.empty()){
                return false;
            }
            if(c == ')' && st.top() != '('){
                return false;
            }
            if(c == '}' && st.top() != '{'){
                return false;
            }
            if(c == ']' && st.top() != '['){
                return false;
            }
            st.pop();
        }
    }
    return st.empty(); //如果栈为空，说明所有左括号都匹配
}

例子二：简单表达式求值

给定一个简单的表达式，其中只包含数字、加号、减号和括号，例如：(1+(4+5+2)-3)+(6+8)，编写程序求出表达式的值：

int calculate(string s){
    stack<int> st_num;  //存储数字
    stack<char> st_op;  //存储运算符
    int num = 0;
    for(int i=0; i<s.size(); i++){
        char c = s[i];
        if(c == ' '){
            continue;
        }
        else if(c == '('){
            st_op.push(c);
        }
        else if(c == ')'){
            while(st_op.top() != '('){
                int num2 = st_num.top();
                st_num.pop();
                int num1 = st_num.top();
                st_num.pop();
                char op = st_op.top();
                st_op.pop();
                int res = op == '+' ? (num1 + num2) : (num1 - num2);
                st_num.push(res);
            }
            st_op.pop();  //弹出左括号
        }
        else if(isdigit(c)){
            num = num * 10 + (c - '0');
            if(i == s.size() - 1 || !isdigit(s[i+1])){
                st_num.push(num);
                num = 0;
            }
        }
        else{ //运算符
            while(!st_op.empty() && st_op.top() != '('){
                int num2 = st_num.top();
                st_num.pop();
                int num1 = st_num.top();
                st_num.pop();
                char op = st_op.top();
                st_op.pop();
                int res = op == '+' ? (num1 + num2) : (num1 - num2);
                st_num.push(res);
            }
            st_op.push(c);
        }
    }
    while(!st_op.empty()){
        int num2 = st_num.top();
        st_num.pop();
        int num1 = st_num.top();
        st_num.pop();
        char op = st_op.top();
        st_op.pop();
        int res = op == '+' ? (num1 + num2) : (num1 - num2);
        st_num.push(res);
    }
    return st_num.top();
}

总结

在本文中，我们详细讲解了C++中Stack（栈）的使用方法与基本操作，并给出了两个应用示例，希望能够帮助读者更好地了解和使用Stack。

阅读剩余 72%