• 02-线性结构4 Pop Sequence


    02-线性结构4 Pop Sequence

    分数 25
    作者 陈越
    单位 浙江大学

    Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

    Input Specification:

    Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

    Output Specification:

    For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

    Sample Input:

    5 7 5
    1 2 3 4 5 6 7
    3 2 1 7 5 6 4
    7 6 5 4 3 2 1
    5 6 4 3 7 2 1
    1 7 6 5 4 3 2
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    Sample Output:

    YES
    NO
    NO
    YES
    NO
    
    • 1
    • 2
    • 3
    • 4
    • 5

    代码长度限制
    16 KB
    时间限制
    400 ms
    内存限制
    64 MB
    C++ (g++)

    思路:

    定义一个结构体,包含栈顶元素的位置、数组、数组大小。
    bool check(vector array,int m,int n)
    检查是否能成功出栈
    定义一个栈s,用cnt来计数。
    s的大小设置为传入的堆栈容量m,栈顶元素置为-1。
    开始遍历输入的序列:
    栈满的话返回false
    否则入栈
    当栈顶元素等于队列的队尾值时,出栈,进行上一个队列元素的匹配。

    如果遍历完序列 即cnt==n,匹配完所有元素,说明按照这些元素的顺序可以顺利出栈,返回true,否则返回false。

    主函数中。输入栈的容量,队列的长度以及需要检查的组数。
    然后输入各个队列元素,进行检查。

    AC代码:

    #include
    using namespace std;
    #define maxsize 1000
    
    struct Node{
        int Top;//记录堆栈顶元素的位置
        int Array[maxsize];
        int Size;
    };
    
    typedef struct Node* Stack;
    
    bool check(vector<int> array,int m,int n)
        //得知道堆栈有多大m,要判断的序列有多大n
    {
        Stack s;
        s=new struct Node;
        int cnt=0;
        s->Size=m;
        s->Top=-1;
        for(int i=1;i<=n;i++)
        {
            if(s->Top+1==s->Size) return false;//栈满
            else s->Array[++s->Top]=i;
            while(s->Array[s->Top]==array[cnt])
            {
                s->Top--;//出栈
                cnt++;//数组往后移
            }
        }
        if(cnt==n) return true;
        else return false;
    }
    
    int main()
    {
        int M,N,K;//M栈 N序列 K组数
        cin>>M>>N>>K;
        vector<int> Array;
        int a;
        for(int i=0;i<K;i++)
        {
            Array.clear();
            for(int j=0;j<N;j++)
            {
                cin>>a;
                Array.push_back(a);
            }
            if(check(Array,M,N)) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
  • 相关阅读:
    JAVA概述
    Android13 大屏设备底部显示TaskBar并NavagatonBar居右
    iEnglish全国ETP大赛:教育游戏助力英语习得
    【Linux】系统api和指令的模拟实现
    什么是微服务?怎么测试?今天一次性讲清楚...
    读书笔记-《ON JAVA 中文版》-摘要2
    win7/10/11电脑浏览器代理服务器是灰色无法更改怎么办 两种解决办法
    今年是嵌入式香还是互联网香?
    474922-26-4,DSPE-PEG-NH2,DSPE-PEG-amine,磷脂-聚乙二醇-氨基饱和18C磷脂
    Linux文件编程详解
  • 原文地址:https://blog.csdn.net/manerzi/article/details/127735982