6

栈 - 博然后深

 2 years ago
source link: https://www.cnblogs.com/boranhoushen/p/16460607.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

栈

1.栈（stack）是一种特殊的线性数据结构，栈中的元素是按照入栈顺序线性的排列。

2.栈的结构如下图所示，仅允许在表的一端进行插入和删除运算，这一端被称为栈顶，相对地，把另一端称为栈底。

2870264-20220709122647311-1551762794.png

3.栈的特点是后进先出（LIFO，Last In First Out），即最后入栈的元素最先出栈。

栈的实现：

数组模拟（手工栈）：

2870264-20220708221947230-2016247530.png

STL栈：

2870264-20220708222408339-1895333037.png

栈的应用：

　　接下来有的小盆友可能会问：“这玩意有啥用？没数组简便，运行还贼慢！”

　　其实在递归函数中，就是不断压栈弹栈的一个过程。

初识应用：

2870264-20220708223553542-1124858493.png

http://ybt.ssoier.cn:8088/problem_show.php?pid=1353

1353：表达式括号匹配(stack)

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 23740     通过数: 12484

【题目描述】

　　假设一个表达式有英文字母（小写）、运算符（+，—，∗，/+，—，∗，/）和左右小（圆）括号构成，以“@@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YESYES”；否则返回“NONO”。表达式长度小于255255，左圆括号少于2020个。

一行数据，即表达式。

一行，即“YESYES” 或“NONO”

【输入样例】

2*(x+y)/(1-x)@

【输出样例】

YES

【样例输入2】

(25+x)*(a*(a+b+b)@

【样例输出2】

NO
【代码】
2870264-20220709120934915-2063640463.png

 这代码乍一看没什么问题，但是…………

2870264-20220709121108972-822123949.png

又去洛古提交了显示“RE”，说明爆栈，但是这个栈怎么变大？？？？？？？？？？？？？？？

于是换了种思路：

 

2870264-20220709121929063-1257079500.png

 两边都AC了！！！

思路都差不多

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    int top=0;
    getline(cin,s);
    for(int i=0;i<s.size()-1;i++){
        if(s[i]=='(') top++;
        else if(s[i]==')') top--;
        if(top<0) break;
    }
    if(top!=0) cout<<"NO";
    else cout<<"YES";
    return 0;
}

栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈栈


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK