队列和栈

前天复习了.Net的栈和队列的用法，为了深入领会下，现在用C++来简单说明一下它们。

队列，先进先出。现在有个问题，有一组0-9的数，要求先将第一个数删除，紧接着将第二个数放在末尾，再将第三个数删除，将第四个数放在末尾，如此反复，直至删除完毕，要求将这组数字按照删除的顺序显示出来。这用队列可以很好的实现。（下图来自百度，侵权删除）

#include <iostream>

using namespace std;

//定义一个结构体，表示队列
struct queue{
int data[100];//队列中的数据
int head;//队列的头
int tail;//队列的尾
};

int main()
{
    struct queue q;
    q.head=0;
    q.tail=0;
    //将数字装入队列
    for(int i=0;i<9;++i)
    {
        cin>>q.data[i];
        q.tail++;
    }
    while(q.head<q.tail)
    {
        cout<<q.data[q.head];
        q.head++;//删除数字就是将队列队首向前走一步
        q.data[q.tail]=q.data[q.head];//将队首放进队尾（第一次时，就是第二个数字放进队尾）
        q.tail++;//队尾要始终指向空的位置
        q.head++;//第一次时，第二个数字放进队尾了，现在要把第二个数字删除掉
    }

    return 0;
}

这时候用队列十分爽。

现在说栈的事情，栈嘛，先进后出，这东西有什么用呢？先提个括号匹配的问题，形如([{}()]),([)]这些括号是否可以正确匹配？（当然第一个是匹配的，第二个不匹配）

下图来自百度，侵权删除

#include <iostream>

using namespace std;

//判断一对括号是否匹配，a代表一个括号，b也应该是一个括号
bool IsPair(char a,char b)
{
    if((a==40&&b==41)||(a==41&&b==40))
        return true;
    if((a==91&&b==93)||(a==93&&b==91))
        return true;
    if((a==123&&b==125)||(a=='}'&&b=='{'))
        return true;
    return false;
}

//问题的主要函数实现
bool IsMatchBrackets(char *p)
{
    //栈定义，就没用结构体
    //top指的是栈顶
    char data[20]={0};
    int top=0;

    //把传进来的字符串首指针赋值给q，当然你也可以直接用p，这里我习惯问题
    char *q=p;
    while(*q)
    {
        //如果匹配，则退栈;否则进栈
        //上面的意思是，如果是一对括号，比如(遇到了)就把(退出数据区
        //如果不是，比如(下面是[,就把[放进数据区
        //以保证栈(数据区)里面的括号至今都仍是单身汪
        if(IsPair((*q),data[top]))
            top--;
        else
        {
            ++top;
            data[top]=*q;
        }
        ++q;
    }

    //判断栈内是否都清空了，如果top==0则括号匹配王朝，数据区没有单身汪了
    //栈内还有，就说明括号没匹配完，还有单身汪，当然就不对了
    if(top==0)
        return true;
    else
        return false;
}

int main()
{
    char str[20]={0};
    cin>>str;
    if(IsMatchBrackets(str))
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

诚惶诚恐，还请大家批评
原文链接: https://www.cnblogs.com/mengnan/p/4896230.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍