两整数序列——栈的相关题解

题目源自剑指offer，今天在hihocoder遇到了基本一样的题所以写了一下
原题为输入两个整数序列，第一个序列表示栈的压入顺序，
请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
输入
第一行：输入N个整数，空格隔开，按先后顺序入栈
第二行：输入N个整数，空格隔开，表示一种出栈顺序
输出
True 或者 False ，意思是第二行数据是否是一个合法的弹出序列
样例输入
1 2 3 4 5
4 5 3 2 1
样例输出
True

大体思路就是借用一个辅助栈，先按压栈顺序压入第一个元素，循环判断出栈顺序与栈顶元素是否相同，相同出栈，不同继续按进栈顺序进栈，最后判断如果辅助栈空即为出栈顺序
值得说的是输入的处理，oj上没定N的具体个数，c/c++来说就取一半一半吧，Java可以分开存两个序列
源码

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class IsPopOrder {
    public static void main(String[] args) {
        ArrayList<Integer> push_list = init();//进栈序列
        ArrayList<Integer> pop_list = init();//出栈序列
        //System.out.println(push + "\n" + pop);
        boolean ans = isPopOrder(push_list, pop_list);
        if(ans)
            System.out.println("True");
        else
            System.out.println("False");
    }

    private static boolean isPopOrder(ArrayList<Integer> push_list, ArrayList<Integer> pop_list) {
        Stack<Integer> stack = new Stack<Integer>();
        int p = 0;
        for(int i = 0; i < push_list.size(); i++) {
            stack.push(push_list.get(i));
            while(!stack.isEmpty()&&stack.peek() == pop_list.get(p)) {
                //栈不空且出栈序列当前元素和栈顶元素相等，出栈
                stack.pop();
                p++;
            }
        }
        return stack.empty();
    
    }

    private static ArrayList<Integer> init() {//输入的特殊处理
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        Scanner in = new Scanner(line);
        ArrayList<Integer> list = new ArrayList<Integer>();
        while(in.hasNextInt()) {
            list.add(in.nextInt());
        }
        return list;
    }

}

c++

#include<stdio.h>
#include<stack>
using namespace std;
 
stack<int> s;
int a[1020],in[510],out[510];
 
int main()
{
    int cnt=0,x;
    while(~scanf("%d",&x))
    {
        a[cnt++]=x;
    }
    if(cnt%2!=0||cnt==0) 
    {  
      printf("False\n");
      return 0;
    }
    for(int i=0;i<cnt/2;i++)
    {
        in[i]=a[i];
    }
    for(int i=cnt/2,j=0;i<cnt;i++,j++)
    {
        out[j]=a[i];
    }
    
    int j=0;
    for(int i=0;i<cnt/2;i++)
    {
        s.push(in[i]);
        while(!s.empty()&&s.top()==out[j])
        {
            j++;
            s.pop();
        }
    }
    if(j==cnt/2) printf("True\n");
    else printf("False\n");
    return 0;
}