• 数据结构与算法之队列和栈的用法
  • Alice 发表于 2015/10/20 23:57:00 | 分类标签: 数据结构 队列的用法 栈的用法
  • 现在有个问题,有一组0-9的数,要求先将第一个数删除,紧接着将第二个数放在末尾,再将第三个数删除,将第四个数放在末尾,如此反复,直至删除完毕,要求将这组数字按照删除的顺序显示出来。这用队列可以很好的实现。
    1. #include <iostream>  
    2. using namespace std;  
    3. //定义一个结构体,表示队列  
    4. struct queue{  
    5. int data[100];//队列中的数据  
    6. int head;//队列的头  
    7. int tail;//队列的尾  
    8. };  
    9.   
    10. int main()  
    11. {  
    12.     struct queue q;  
    13.     q.head=0;  
    14.     q.tail=0;  
    15.     //将数字装入队列  
    16.     for(int i=0;i<9;++i)  
    17.     {  
    18.         cin>>q.data[i];  
    19.         q.tail++;  
    20.     }  
    21.     while(q.head<q.tail)  
    22.     {  
    23.         cout<<q.data[q.head];  
    24.         q.head++;//删除数字就是将队列队首向前走一步  
    25.         q.data[q.tail]=q.data[q.head];//将队首放进队尾(第一次时,就是第二个数字放进队尾)  
    26.         q.tail++;//队尾要始终指向空的位置  
    27.         q.head++;//第一次时,第二个数字放进队尾了,现在要把第二个数字删除掉  
    28.     }  
    29.     return 0;  
    30. }  

    这时候用队列十分爽。

    现在说栈的事情,栈嘛,先进后出,这东西有什么用呢?先提个括号匹配的问题,形如([{}()]),([)]这些括号是否可以正确匹配?(当然第一个是匹配的,第二个不匹配)
    1. #include <iostream>  
    2. using namespace std;  
    3. //判断一对括号是否匹配,a代表一个括号,b也应该是一个括号  
    4. bool IsPair(char a,char b)  
    5. {  
    6.     if((a==40&&b==41)||(a==41&&b==40))  
    7.         return true;  
    8.     if((a==91&&b==93)||(a==93&&b==91))  
    9.         return true;  
    10.     if((a==123&&b==125)||(a=='}'&&b=='{'))  
    11.         return true;  
    12.     return false;  
    13. }  
    14.   
    15. //问题的主要函数实现  
    16. bool IsMatchBrackets(char *p)  
    17. {  
    18.     //栈定义,就没用结构体  
    19.     //top指的是栈顶  
    20.     char data[20]={0};  
    21.     int top=0;  
    22.   
    23.     //把传进来的字符串首指针赋值给q,当然你也可以直接用p,这里我习惯问题  
    24.     char *q=p;  
    25.     while(*q)  
    26.     {  
    27.         //如果匹配,则退栈;否则进栈  
    28.         //上面的意思是,如果是一对括号,比如(遇到了)就把(退出数据区  
    29.         //如果不是,比如(下面是[,就把[放进数据区  
    30.         //以保证栈(数据区)里面的括号至今都仍是单身汪  
    31.         if(IsPair((*q),data[top]))  
    32.             top--;  
    33.         else  
    34.         {  
    35.             ++top;  
    36.             data[top]=*q;  
    37.         }  
    38.         ++q;  
    39.     }  
    40.   
    41.     //判断栈内是否都清空了,如果top==0则括号匹配王朝,数据区没有单身汪了  
    42.     //栈内还有,就说明括号没匹配完,还有单身汪,当然就不对了  
    43.     if(top==0)  
    44.         return true;  
    45.     else  
    46.         return false;  
    47. }  
    48. int main()  
    49. {  
    50.     char str[20]={0};  
    51.     cin>>str;  
    52.     if(IsMatchBrackets(str))  
    53.         cout<<"Yes"<<endl;  
    54.     else  
    55.         cout<<"No"<<endl;  
    56.     return 0;  
    57. }  
  • 请您注意

    ·自觉遵守:爱国、守法、自律、真实、文明的原则

    ·尊重网上道德,遵守《全国人大常委会关于维护互联网安全的决定》及中华人民共和国其他各项有关法律法规

    ·严禁发表危害国家安全,破坏民族团结、国家宗教政策和社会稳定,含侮辱、诽谤、教唆、淫秽等内容的作品

    ·承担一切因您的行为而直接或间接导致的民事或刑事法律责任

    ·您在编程中国社区新闻评论发表的作品,本网站有权在网站内保留、转载、引用或者删除

    ·参与本评论即表明您已经阅读并接受上述条款

  • 感谢本文作者
  • 作者头像
  • 昵称:Alice
  • 加入时间:2013/6/13 0:00:00
  • TA的签名
  • 这家伙很懒,虾米都没写
  • +进入TA的空间
  • 以下内容也很赞哦
分享按钮