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
Sample Output:
YES
NO
NO
YES
NO
题目的意思是，给我们一个固定的栈容量大小的栈（m表示栈容量），进栈n个数，最后给我们k组出栈序列，让我们判断是否是正确的出栈序列。
我想到了三种办法，最后只要一种成功了。
一开始，我想着找出某种规律，然后用改规律一组一组判断出栈序列的正确性，但是很遗憾失败了。
之后，我觉得给定n个数进栈，我把所有的出栈序列全部存到n个数组中，但是求出所有正确的出栈序列过于复杂，我没去尝试。
最好的办法就是模拟。
我们声明一个栈，用来模拟，把要测试的出栈序列放入数组中，然后for循环1-n一直进栈，然后进栈取栈顶元素和数组里的元素对比，一样则出栈，最后判断栈是否为空，空的话就说明是正确的出栈序列。这里我是用我写的栈函数来写的。。。。。。主函数代码几乎每段都写了注释
|
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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
#include<bits/stdc++.h> using namespace std; //自己写的链式栈 //要实现的操作有： 初始化栈initstack ， 销毁栈destroystack ， 判断栈空emptystack // 取栈顶元素 gettop 进栈pushstack ， 出栈popstack , 打印栈元素printstack typedef struct linknode{ int data; struct linknode *next; }sqstack; void initstack(sqstack*&st){ st=(sqstack*)malloc(sizeof(sqstack)); st->next=NULL; } void destroystack(sqstack*&st){ sqstack *pre=st,*p=st->next; while(p){ free(pre); pre=p; p=pre->next; } free(pre); } bool emptystack(sqstack*st){ return(st->next==NULL); } int gettop(sqstack*st){//栈空的时候请不要用这个函数 return st->next->data; } void pushstack(sqstack*&st,int e){ sqstack*p; p=(sqstack*)malloc(sizeof(sqstack)); p->data=e; p->next=st->next; st->next=p; } bool popstack(sqstack*&st){ if(st->next==NULL) return false; // st->next=st->next->next; // free(st->next); // return true; sqstack *p; p=st->next; //p指向首结点 st->next=p->next;//删除首结点 free(p); return true; } void printstack(sqstack*st){ st=st->next;//栈的头结点是没有数据的 while(st){ cout<<st->data<<" "; st=st->next; } } int main(){ int m,n,k; int p,q;//虚拟表示链栈满了，q虚拟实现数组的递增 int i,j; bool bl; //题目中没有说n的大小，那我先读入n，声明一个动态数组 cin>>m>>n>>k; int a[n+2]; while(k--){ sqstack *link; initstack(link); p=0; for(i=1;i<=n;i++) cin>>a[i]; q=1; //开始模拟 for(int i=1;i<=n;i++){ pushstack(link,i);//一直进栈 p++;//进栈成功后长度加一 //此时要判断栈满，这时需要我们的p了 if(p>m) break; j=gettop(link); while(a[q]==j){ //匹配成功，出栈，并且q+1； popstack(link); p--;//这里一定要记得减一，找了好久 q++; //下面这三条代码，是因为我写的取栈顶函数不好，不能再自动判断栈为空 bl=emptystack(link); if(bl) break; j=gettop(link); } } bl=emptystack(link); if(bl) cout<<"YES"<<endl; else cout<<"NO"<<endl; destroystack(link);//这里一定要记得销毁栈 } } |
