本文共 2309 字，大约阅读时间需要 7 分钟。

1051 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 51 2 3 4 5 6 73 2 1 7 5 6 47 6 5 4 3 2 15 6 4 3 7 2 11 7 6 5 4 3 2

Sample Output:

YESNONOYESNO

我的代码：

我的思路：用栈和队列来模拟

队列存输入的出栈顺序。栈初始为空。

n个要进栈的元素从1到n遍历一遍：

               （1）将当前元素入栈。

               （2）判断栈顶元素和队列首元素是否相等，如果相等，栈顶元素出栈，队列首元素出队

                    （2）这个地方这样写：

while(a.top()==s.front()&&!a.empty())	    	{	    	        a.pop();	    		s.pop();	    		if(a.empty())	    		break;	    		if(a.size()>=m)	    		break;		}

因为判断栈顶元素时，栈有可能为空，所以里面要加一个是否为空的判断，还有就是栈容量的判断，是>=,而非==。

最后，再判断栈是否为空，空则YES，反之NO。

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int main(){	queue
       
         s;	stack
        
          a; while(!a.empty()) { a.pop(); } while(!s.empty()) { s.pop(); } int m,n,k,i,j,t; cin>>m>>n>>k; for(i=0;i
         
          >t; s.push(t); } for(j=1;j<=n;j++) { a.push(j);// cout<
          
           <
           
            =m) break; } } if(!a.empty()) cout<<"NO"<
           
          
         
        
       
      
     
    
   

别人的代码：

#include
   
    using namespace std;stack
    
     st;int digit[1005];int main() {    int n, m ,t;    cin>> m >>n >>t;    while(t--)    {    	while(!st.empty())    		st.pop();    	for(int i = 1; i <= n; i++)    		scanf("%d",&digit[i]);    	int cnt = 1;    	int flag = 1;		for(int i = 1; i <= n; i++)    	{    		st.push(i);    		if(st.size() > m){    			flag = 0;    			break; //表示当前已经大于了 			}    		while(!st.empty() && st.top() == digit[cnt])     		{    			st.pop();    			cnt++;			}		}		if(st.empty() && flag)			cout<<"YES"<
    
   

不建议用万能头文件！

转载地址：http://tuven.baihongyu.com/