• 数据结构01 栈及其相关问题讲解【C++实现】

    栈是一种线性数据结构，栈的特征是数据的插入和删除只能通过一端来实现，这一端称为“栈顶”，相应的另一端称为“栈底”。

     

    栈及其特点

    用一个简单的例子来说，栈就像一个放乒乓球的圆筒，底部是封住的，如果你想拿出乒乓球，只能从顶部拿。同样的，如果你想再将乒乓球放回去，也只能从顶部放入其中。当然生活中还有很多这样的例子，再比如食堂中的一叠盘子，我们只能从顶端一个一个的取。放盘子也只能放在最上方。

    总结栈的特点为：先入后出(Last In First Out->LIFO)，即先入栈的元素要在之后入栈的元素取出来之后才能取出来。

    STL模板中栈的基本使用

    对于栈的使用，我们可以直接利用STL模板来实现，STL模板库中栈的基本操作如下：

     头文件：#include<堆栈>

    创建一个存放int类型数据的空栈s：stack s;

    s.empty():  判断栈是否为空，为空返回true，否则返回false；

    s.size():  返回栈中元素的个数；

    s.top():  获取栈顶元素的值；

    s.push(k):   向栈中添加新的元素k；

    s.pop():    删除栈s的栈顶元素。

    s.push(k):   向栈中添加新的元素k；

    s.pop():    删除栈s的栈顶元素。

     

    训练：逆波兰表达式

    逆波兰表达式，又称后缀表达式，后缀表达式不包含括号，运算符(包括'+''-''*''/')放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：(2 + 1) * 3 ， 即2 1 + 3 *。利用栈结构，将后缀表达式的结果计算出。

    【输入描述】输入一个逆波兰表达式，字符之间用空格隔开

    【输出描述】输出算式结果

    【输入样例】2 1 + 3 *

    【输出样例】9

     

    参考程序

    1. #include
    2. #include
    3. using namespace std;
    4. int main(){
    5.   int t,k;
    6.   char c;
    7.   stack<int> s;
    8.   while(cin>>c){
    9.         if(c>='0'&&c<='9')
    10.             s.push(c-'0');  //是数字就入栈
    11.         if(c=='+'){
    12.             t=s.top(); //获取栈顶数字
    13.             s.pop();   //出栈
    14.             k=s.top(); //获取新的栈顶
    15.             s.pop();     //出栈
    16.             s.push(t+k);   //相加的和入栈
    17.         }
    18.         if(c=='-'){
    19.             t=s.top();   //获取栈顶
    20.             s.pop();     //出栈
    21.             k=s.top();  //获取新的栈顶
    22.             s.pop();     //出栈
    23.             s.push(k-t); //相减结果入栈，注意顺序
    24.         }
    25.         if(c=='*'){
    26.             t=s.top();
    27.             s.pop();
    28.             k=s.top();
    29.             s.pop();
    30.             s.push(t*k);   //相乘的积入栈
    31.         }
    32.         if(c=='/'){
    33.             t=s.top();
    34.             s.pop();
    35.             k=s.top();
    36.             s.pop();
    37.             s.push(k/t); //相除结果入栈注意顺序
    38.         }
    39.     }
    40.     cout<top();
    41.     return 0;
    42. }

    训练：括号匹配

    给定一个字符串，里边可能包含“()”、“[]”、“{}”三种括号，请编写程序检查该字符串的括号是否匹配出现,匹配说明嵌套关系正确，例如 {[()]}() 是匹配的,而)({)[}]( 则不匹配。匹配则输出YES，否则输出NO。）

    【输入描述】输入一个字符串 例如(1+2)/(0.5+1)

    【输出描述】如果字符串匹配则输出YES，否则输出NO

    【输入样例】(1+2)/[(0.5+1)*2]

    【输出样例】YES

    参考程序

    1. #include 
    2. #include 
    3. using namespace std;
    4. int main(){
    5.     stack<char> s;
    6.     string a;
    7.     cin>>a;
    8.     for(int i=0;isize();i++){
    9.         if(a[i]=='('||a[i]=='['||a[i]=='{')  s.push(a[i]); //左括号入栈
    10.         if(a[i]==')'){
    11.             if(s.empty()) //右括号没匹配的就no
    12.             {
    13.                 cout<<"NO"<
    14.                 return 0;
    15.             }
    16.             if(s.top()=='(')s.pop(); //右括号有匹配的则出栈
    17.         }
    18.         if(a[i]==']'){
    19.             if(s.empty()) //右括号没匹配的就no
    20.             {
    21.                 cout<<"NO"<
    22.                 return 0;
    23.             }
    24.             if(s.top()=='[') s.pop(); //右括号有匹配的则出栈
    25.         }
    26.         if(a[i]=='}'){
    27.             if(s.empty()) //右括号没匹配的就no
    28.             {
    29.                 cout<<"NO"<
    30.                 return 0;
    31.             }
    32.             if(s.top()=='{') s.pop(); //右括号有匹配的则出栈
    33.         }
    34.     }
    35.     if(s.empty()) cout<<"YES"<
    36.     else cout<<"NO"<
    37.     return 0;
    38. }

    从入门到算法，再到数据结构，查看全部文章请点击此处icon-default.png?t=N7T8http://www.bigbigli.com/

  • 相关阅读:
    CUDA 学习记录
    我从自动化测试转为测试开发，资深测试总结测试开发技术栈，提升之路......
    香港Web3.0生态现状
    Linux 安装Harbor镜像仓库私服
    1.2 ElasticSearch核心术语
    ffmpeg 视频剪切与合并，时间不精确的问题
    深度学习之基础知识
    基于物联网的智能晾衣架研发
    docker-compose安装和初体验
    常用数据结构 ——— 队列（环形队列和顺序队列）
  • 原文地址：https://blog.csdn.net/qq_39434533/article/details/139632667