网站站内搜索怎么做,wordpress默认主题修改,百度怎么发自己的小广告,app设计思路怎么写一.什么是栈
堆栈又名栈#xff08;stack#xff09;#xff0c;它是一种运算受限的数据结构#xff08;线性表#xff09;#xff0c;只不过他和数组不同#xff0c;数组我们可以想象成一个装巧克力的盒子#xff0c;你想拿一块巧克力#xff0c;不需要改变其他巧克…一.什么是栈
堆栈又名栈stack它是一种运算受限的数据结构线性表只不过他和数组不同数组我们可以想象成一个装巧克力的盒子你想拿一块巧克力不需要改变其他巧克力的位置而栈就相当于是一个只有上方有一个口且宽度只能容纳一块巧克力的盒子如图 那如果我们想拿最下面的巧克力该怎么办呢就需要把这颗巧克力上面的所有巧克力都取出这样才能取出最下面的巧克力。我们可以把栈想象成是一个封了底的数组要想拿走一个值就需要把它上面的所有值都取出同理如果我们想加入一个数据也只能加到栈的最顶端。这就是栈。
二.栈的具体实现
1.手写栈
如果要手写一个栈我们优先选择用和栈差别最小的数组模拟栈我们要想模拟一个栈需要拥有几个操作函数如下。
①我们要编写push函数作用是往栈里输入数据 要想编写这样一个函数我们首先需要确定数组栈的顶端再把数放进去。我们可以定义一个栈的长度变量初始值为0你每输入一个数据就。这样就可以很好的解决栈的输入了我们看代码
void push(char x) { //top是栈的长度M是所模拟的数组的长度s是栈的名字x是要往栈顶放的数if(topM) { //判断栈的长度不超过模拟它的数组的长度则可以输入。top; //将栈顶s[top]x; //把栈顶值设为x}
}
②我们要编写GetTop 函数作用是获取栈顶的值 这个很简单我们直接获取数组的第top项就可以了。我们看代码
char getTop() {return s[top]; //返回栈顶元素
}
③我们要编写弹栈函数目的是删除栈顶元素以取出下一个元素。 我们可以直接让top--这样原来的栈顶元素就不在这个栈中了也就删除了栈顶元素。我们看代码:
void pop() {if(top0) { //如果栈不空top--; //删除栈顶元素}
}
④我们要编写Getlen函数目的是获取栈的长度。 由于top就是代表着栈顶元素的位置所以我们只要返回top的值就可以了。我们看代码
int getlen() {return top;
}
接下来把所有函数都放在一起发个程序
#includeiostream
using namespace std;
const int M10; //M大小可动态调整
int s[M1];
int top0;
void push(int x) {if(topM) {top;s[top]x;}
}
void pop() {if(top0) {top--;}
}
int getTop() {return s[top];
}
int getlen() {return top;
}int main() {return 0;
}
二.STL模板
有的人可能会说手写栈实在太麻烦了有没有简单的方法呢当然有接下来我就给大家讲。
STL模板不需要你手动定义栈中的函数他已经给你定义好了函数和对应的栈也不用你再用数组模拟了。但想用这个定义好了的栈我们要导入一个头文件如下
#includestack
一切准备就绪我们要想定义一个STL栈需要用如下代码
stackints;
就是stack后面尖括号里写数据类型然后再写一个栈名就可以了。
STL栈里面有一些常用的函数。
1.push作用是往栈里输入一个数据只不过是用栈名.push(输入的数据的方式输入。如下
s.push(x) 2.top和上面的Gettop函数的作用相同。也需要用栈名.top()的方式来调用。如下
s.top();
3.pop和上面的pop作用相同。如下
s.pop();
4.size和上面的Getlen函数作用相同。如下
s.size();
三.例题 题目描述 假设一个表达式有英文字母小写、运算符、-、*、/和左右小圆括号构成以 作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配若匹配则输出 YES否则输出 NO。表达式长度小于 255左圆括号少于 20 个。 输入格式 一行表达式。 输出格式 一行YES 或 NO。 输入输出样例 输入 #1复制 2*(xy)/(1-x)输出 #1复制 YES输入 #2复制 (25x)*(a*(abb)输出 #2复制 NO说明/提示 表达式长度小于 255左圆括号少于 20 个。 程序 (装逼代码
#includebits/stdc.h
using namespace std;
stackchar a;
int main() {string s;cins;for(int i0; is.length(); i) {if(s[i]() {a.push(s[i]);}if(s[i])) {if(a.size()1a.top()() {a.pop();} else {coutNO;return 0;}}}if(a.size0)coutYES;else coutNO;return 0;
}
