题解 | #栈的压入、弹出序列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型一维数组 
     * @param popV int整型一维数组 
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        if(pushV.length == 1){
            return pushV[0] == popV[0];
        }

        boolean result = false;
        Stack stack = new Stack();
        Set<Integer> stackSet = new HashSet<>(pushV.length);
        int pushCount = 0;
        int popCount = 0;
        //第一次入栈
        push(stack,stackSet,pushV[pushCount++]);

        while(true){
            if(pushCount <= 1000 && popCount <= pushCount && stackSet.contains(popV[popCount])){
                int popValue = stack.top();
                if(popValue == popV[popCount]){
                    stack.pop();
                    popCount++;
                }else{
                    result = false;
                    break;
                }
            }else{
                if(pushCount == pushV.length && popCount < pushCount){
                    result = false;
                    break;
                }
                push(stack,stackSet,pushV[pushCount++]);
            }
            if(pushCount == popCount && popCount == pushV.length){
                result = true;
                break;
            }
        }

        return result;
    }

    public static void push(Stack stack,Set<Integer> stackSet,int value){
        stack.push(value);
        stackSet.add(value);
    }

    public static class Stack{
        private Node head;
        private Node tail;
        private int length = 0;

        public void push(int value){
            length++;
            if(head == null){
                head = new Node(value);
                head.next = null;
                tail = head;
            }else{
                Node next = head;
                head = new Node(value);
                head.next = next;
            }
        }

        public int pop(){
            if(length == 0){
                return -1;
            }else{
                length--;
                int popValue = head.value;
                head = head.next;
                return popValue;
            }
        }

        public int top(){
            if(length == 0){
                return -1;
            }else{
                int popValue = head.value;
                return popValue;
            }
        }
    }

    public static class Node{
        private int value;
        private Node next;

        public Node(int value){
            this.value = value;
        }

        public void setValue(int value){
            this.value = value;
        }

        public int getValue(){
            return value;
        }

        public void setNext(Node next){
            this.next = next;
        }

        public Node getNext(){
            return next;
        }
    }


}