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。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++中Stack(栈)的使用方法与基本操作详解 - Python技术站