当前位置:编程学习 > C/C++ >>

栈的压入压出

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。
输入:
每个测试案例包括3行:
第一行为1个整数n(1<=n<=100000),表示序列的长度。
第二行包含n个整数,表示栈的压入顺序。
第三行包含n个整数,表示栈的弹出顺序。
输出:
对应每个测试案例,如果第二个序列是第一个序列的弹出序列输出Yes,否则输出No。
样例输入:
5
1 2 3 4 5
4 5 3 2 1
5
1 2 3 4 5
4 3 5 1 2
样例输出:
Yes
No
代码AC:
思想:扫描 + 入栈 + 弹栈:当前的输出==栈顶元素,弹栈,若当前输出的不是栈顶元素,那么就要将元素入栈直到此元素,如果入栈中没有发现此元素,那么就是错误的序列。
[cpp]  
#include <stdio.h>  
#include <stdlib.h>  
  
int main()  
{  
    int n, *stack1, *stack2, *stack, i, j, top = -1, flag, f;  
      
    while( scanf("%d", &n) != EOF )  
    {  
           stack1 = ( int * )malloc( sizeof( int ) * n );  
           stack2 = ( int * )malloc( sizeof( int ) * n );  
           stack  = ( int * )malloc( sizeof( int ) * n );  
             
           for( i = 0; i < n; i++ )  
           {  
                scanf("%d", &stack1[i]);  
           }  
             
           for( i = 0; i < n; i++ )  
           {  
                scanf("%d", &stack2[i]);  
           }  
             
           top = -1;  
           i = 0;  
           j = 0;             
           flag = 1;  
             
           while( stack1[i] != stack2[j] )  
           {  
                  stack[++top] = stack1[i];  
                    
                  if( ( ++i ) >= n )  
                  {  
                      printf("No\n");  
                      flag = 0;  
                      break;  
                  }  
           }  
             
           if( !flag )  
           {  
               continue;  
           }  
              
           i++;  
           j++;  
             
           while( j < n )  
           {  
                  f = 0;  
                    
                  if( top > -1 )  
                  {  
                      if( stack2[j] == stack[top] )  
                      {  
                          top--;  
                          j++;  
                      }  
                      else  
                      {  
                          f = 1;  
                      }  
                  }  
                  else  
                  {  
                      f = 1;  
                  }  
                    
                  if( f )  
                  {  
                      while( stack2[j] != stack1[i] )  
                      {  
                             stack[++top] = stack1[i];  
                             i++;  
                             if( i >= n )  
                             {  
                                 printf("No\n");  
                                 flag = 0;  
                                 break;  
                             }  
           
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,