数据结构----栈与队列

2019-10-03   数据结构

:后进先出: 最后插入的元素最先出来。

队列:先进先出: 最先插入的元素最先出来。

堆、列表、队列和栈

SDUT OJ题集

1.数据结构实验之栈与队列一:进制转换

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    int n,r,k;
    int a[200];
    int i;
    scanf("%d",&n);
    scanf("%d",&r);
    if(n==0)//输出0的情况
    {
        printf("%d",n);
    }
    else
    {
        k=0;
        while(n!=0)
        {
            int j=n%r;//取余 1279%8=7 1279/8=159  159%8=7 ...
            a[k++]=j;//存数组
            n=n/r;//下一位
        }
        for(i=k-1;i>=0;i--)
        {
            printf("%d",a[i]);
        }
    }
    return 0;
}

2.数据结构实验之栈与队列二:一般算术表达式转换成后缀式

关于后缀表达式

#include <stdio.h>
#include <string.h>
int f(char ch, char sh)//比较优先级
{
    if(sh=='(') return 1;
    if( (ch=='*' || ch=='/' || ch=='%')&&( sh=='+' || sh=='-')  )
        return 1;
    else
        return -1;
}
int main()
{
    int i = 0 , n , top = -1 ;
    char exp[1000] , str[1000] , ch ;
    while(scanf("%c", &ch) && ch != '#')
    {
        if(ch >= 'a' && ch <='z')//如果是数字直接存入字符串数组中
            exp[i++] = ch ;
        else if(ch=='(')//如果是( 将其压入栈中
            str[++top] = ch ;
        else if(ch==')')//如果是 )弹栈
        {
            while(top!=-1)
            {
                exp[i++] = str[top];
                top--;
                if(str[top]=='(')//到( 时停止
                {
                    top--;
                    break;
                }
            }
        }
        else
        {
            if(top == -1 || f(ch,str[top]) > 0 )//若是操作符,如果栈空或者该操作符的优先级大于栈顶操作符则将其放入到栈中。
                str[++top] = ch ;
            else
            {
                while(top >=0 && f(ch,str[top]) < 0  )
                {
                    exp[i++] = str[top--];//如果该操作符的优先级小于等于栈顶操作符则弹出栈中的操作符存入字符串exp[]中,
                }
                str[++top] = ch ;//直到该操作符的优先级大于栈顶操作符或栈空,然后将该操作符入栈。
            }
        }
    }
    while(top != -1)
    {
        exp[i++] = str[top--];//当读到了中缀式的末尾时,如果栈非空则将栈中所有元素依次弹出存入字符串exp[]中,最后见‘\0’存入exp[]中,则exp[]中存储的就是后缀表达式。
    }
    exp[i] = '\0';
    printf("%s\n", exp);
    return 0;
}

3.数据结构实验之栈与队列三:后缀式求值

参考博客

#include<stdio.h>
#include<string.h>
int top=0,i,b[1000];
int main()
{
    char s;
    while(scanf("%c",&s),s!='#')//#结束
    {
        if(s>='0'&&s<='9')//字符化成数字
        {
            b[++top]=s-'0';
        }
        else if(s=='+'||s=='-'||s=='*'||s=='/')//各种运算
        {
            if(s=='+')
            {
                b[top-1]=b[top-1]+b[top];
                top--;
            }
            if(s=='-')
            {
               b[top-1]=b[top-1]-b[top];
                top--;
            }
            if(s=='*')
            {
                b[top-1]=b[top-1]*b[top];
                top--;
            }
            if(s=='/')
            {
                b[top-1]=b[top-1]/b[top];
                top--;
            }
        }
    }
    printf("%d\n",b[top]);
    return 0;
}

4.数据结构实验之栈与队列四:括号匹配

#include <stdio.h>
int main()
{
    int i , n , top ;
    char s[51] , str[51] , a ;
    while(gets(s))
    {
        top = -1 ;
        for(i = 0 ; s[i] != '\0' ; i++)
        {
            if(s[i]=='(' || s[i]=='[' || s[i]=='{')//入栈
                str[++top] = s[i] ;
            if(s[i]==')' || s[i]==']' || s[i]=='}')
            {
                a = str[top] ;//栈顶(后进先出)即最后一个元素
                top-- ;
                if(a=='(' && s[i]==')' ||a=='[' && s[i]==']' || a=='{' && s[i]=='}' )//匹配
                    ;
                else
                    break;
            }
        }
        if(s[i]=='\0' && top == -1)//如果一一匹配即top=-1,全部匹配
            printf("yes\n");
        else
            printf("no\n");
    }
}

5.数据结构实验之栈与队列五:下一较大值(一)

#include <stdio.h>
int main()
{
    int t,top,flag,n;
    int i;
    int a[1001],b[1001],s[1001];
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            top=0;
            scanf("%d",&n);
            for(i=0; i<n; i++)
            {
                scanf("%d",&a[i]);
            }
            b[n-1]=-1;
            for(i=n-2; i>=0; i--)//倒序
            {
                flag=0;
                if(a[i+1]>a[i])//入栈
                {
                    s[++top]=a[i+1];
                    b[i]=a[i+1];//存储每个数的下一个较大值
                }
                else
                {
                    while(top!=0)
                    {
                        if(s[top]>a[i])//最大值情况
                        {
                            flag=1;
                            b[i]=s[top];
                            break;
                        }
                        top--;
                    }
                    if(flag==0)
                    {
                        b[i]=-1;//最大值情况
                    }
                }
            }
            for(i=0; i<n; i++)
            {
                printf("%d-->%d\n",a[i],b[i]);
            }
            if(t)
            {
                printf("\n");
            }
        }
        }
        return 0;
}

6.数据结构实验之栈与队列六:下一较大值(二)

#include <stdio.h>
int main()
{
    int t,top,flag,n;
    int i;
    int a[100001],b[100001],s[100001];
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            top=0;
            scanf("%d",&n);
            for(i=0; i<n; i++)
            {
                scanf("%d",&a[i]);
            }
            b[n-1]=-1;
            for(i=n-2; i>=0; i--)//倒序
            {
                flag=0;
                if(a[i+1]>a[i])//入栈
                {
                    s[++top]=a[i+1];
                    b[i]=a[i+1];//存储每个数的下一个较大值
                }
                else
                {
                    while(top!=0)
                    {
                        if(s[top]>a[i])
                        {
                            flag=1;
                            b[i]=s[top];
                            break;
                        }
                        top--;
                    }
                    if(flag==0)
                    {
                        b[i]=-1;
                    }
                }
            }
            for(i=0; i<n; i++)
            {
                printf("%d-->%d\n",a[i],b[i]);
            }
            if(t)
            {
                printf("\n");
            }
        }
        }
        return 0;
}

7.数据结构实验之栈与队列七:出栈序列判定

参考博客 有点难理解

#include<stdio.h>
int main()
{
    int i,j,top,n,t;
    int a[10005]={-1};
    int b[10005]={-1};
    int c[10005]={-1};
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&t);
    while(t--)
    {
        for(j=0;j<n;j++)
        {
            scanf("%d",&b[j]);
        }
        i=0;                
        j=0;
        top=-1;
        while(j<n)                 //a[]数组的意思是等待要进入栈的全部元素
        {                          //b[]数组的意思是出栈的元素序列
            if(a[i]==b[j])         //c[]数组的意思是已经在栈中的元素       
            {                      //a[i]代表当前正要进栈的元素,如果a[i]==b[j]。      
                i++;               //说明此元素与序列当前首元素相同,说明此元素刚进栈就出栈      
                j++;               //如果a[i]!=b[j]说明此元素并没有立即出栈,       
            }                      //则成为栈中元素,也就是c[]数组中的元素,再次之前我们要判断       
            else if(top!=-1&&c[top]==b[j])//下面这一步,也就是c[top]==b[j],                              
            {                //看看当上一步的元素因为a[i]==b[j]出栈之后,它在栈中的下一个的元素是否出栈               
                j++;          
                top--;//出栈      
            }
            else if(i<n)
            {
                c[++top]=a[i];//将上一步a[i]!=b[j]的a[i]元素进栈
                i++;
            }
            else
                break;
        }
        if(top==-1)     //判断栈内元素是否为空
        {
            printf("yes\n");
        }
        else
        {
            printf("no\n");
        }
    }
    return 0;
}

8.数据结构实验之栈与队列八:栈的基本操作

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int t;
    int m,n;
    char c;
    int x;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&m,&n);
        int a[1001];
        int top=0;
        while(n--)
        {
            scanf("%c",&c);
            if(c=='\n');//空行
            scanf("%c",&c);
            if(c=='P')
            {
                scanf("%d",&x);
                if(top>=m)
                {
                    printf("F\n");
                }
                else
                {
                    top++;
                    a[top]=x;
                }
            }
            else if(c=='A')
            {
                if(top==0)
                {
                    printf("E\n");

                }
                else
                {
                    printf("%d\n",a[top]);

                }
            }
            else if(c=='O')
            {
                if(top==0)
                {
                    printf("E\n");
                }
                else
                {
                    printf("%d\n",a[top]);
                    top--;
                }
            }
        }
        if(t)  //每组数据输出空行最后一组没有
        {
            printf("\n");
        }
    }
    return 0;
}

9.数据结构实验之栈与队列九:行编辑器

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char b[251];
int main()
{
    int i,len,top;
    char a[251];
    while(gets(a))
    {
        top=0;
        len=strlen(a);
        for(i=0; i<len; i++)
        {
            if(a[i]=='#')//退格
            {
                if(top==0)
                    ;
                else
                    top--;

            }
            else if(a[i]=='@')//退行
            {
                if(top==0)
                    ;
                else
                {
                    while(top!=0)
                        top--;
                }
            }
            else
                b[top++]=a[i];//入栈
        }
        if(top!=0)
        {
            for(i=0; i<top-1; i++)
                printf("%c",b[i]);
            printf("%c\n",b[i]);
        }
        else
            ;

    }
    return 0;
}

10.数据结构实验之栈与队列十:走迷宫

#include<bits/stdc++.h>
using namespace std;
int n,m;
int step = 0;
int a[1000][1000],e[1000][1000];
void dfs(int x,int y)
{
    int next[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};  //四个方向
    int tx,ty;
    if(x == n&&y == m)  //判断是否到达出口位置
    {
         step ++;   //找到一次记录一次
         return ;    
    }

    for(int i=0;i<=3;i++)
    {
        //下一个点的坐标
        tx = x + next[i][0];
        ty = y + next[i][1];
        //判断是否越界
        if(tx < 1 || tx > n || ty <1 || ty > m)
            continue;
            //判断该点是否能走或者已经在路上
        if(e[tx][ty] == 0 && a[tx][ty] == 0)
        {
            a[tx][ty] = 1;  //标记这个点已被走过
            dfs(tx,ty);   //开始尝试下一个点
            a[tx][ty] = 0;  //当尝试结束时取消标记
        }
    }
    return ;
}
int main()
{
    int T;
    int i,j;
    scanf("%d",&T);
    while(T--)
    {
        step = 0;
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%d",&e[i][j]);
            }
        }
        a[1][1] = 1;
        dfs(1,1);
        printf("%d\n",step);
    }
    return 0;
}

11.数据结构实验之栈与队列十一:refresh的停车场

#include<bits/stdc++.h>
using namespace std;
string a[20010],b[20010];
int main()
{
    int n,m,i,flag;
    string x,y;
    while(cin>>n>>m)
    {
        flag=0;
        int top=0;
        int top1=0;
        int top2=0;
        for(i=0;i<m;i++)
        {
            cin>>x;
            if(x=="Add")
            {
                cin>>y;
                if(top<n)
                {
                    a[++top]=y;//停车场
                }
                else
                {
                    b[++top1]=y;//通道队
                }
            }
            if(x=="Del")
            {
                if(top<=0)
                {
                    flag=1;
                }
                else if(top2<=top1)//一前一后
                {
                    a[top]=b[++top2];//便道最前面车进入停车场
                }
                else if(top2>top1)//便道没有车 
                {
                    top--;
                }
            }
            if(x=="Out")
            {
                if(top2>top1)//便道没有车
                {
                    flag=1;
                }
                else//便道最前面的车辆不再等待,放弃进入停车场所以是top2
                {
                    top2++;
                }
            }
        }
            if(top>0 && flag==0)
            {
                while(top>0)
                {
                    cout<<a[top--]<<endl;
                }
            }
            else
                cout<<"Error"<<endl;
    }
    return 0;
}