public class Pet{
    private String type;
    public Pet(String type){this.type = type;}
    public String getType(){ return type;}
}

public class Cat {
   public Cat(){ super("cat");}
}
public class Dog {
   public Dog(){ super("dog");}
}

public class PetQueenElement{
    private Pet pet;
    private int order;

    PetQueenElement(Pet pet, int order){
        PetQueenElement element = new PetQueenElement(pet, order);
    }

    public Pet getPet(){
        return this.pet;
    }

    public int getOrder(){
        return this.order;
    }
}

public class PetQueen{
    private int order;
    private Queen<PetQueenElement> cats;
    private Queen<PetQueenElement> dogs;

    public PetQueen(){
        this.cats = new LinkedList<>();
        this.dogs = new LinkedList<>();
        this.order = 0;
    }

    public void add(Pet pet){
        if(pet instanceof Cat){
            cats.add(new PetQueenElement(pet, order)));
        }else{
            dogs.add(new PetQueenElement(pet, order)));;
        }
        allPets.add(pet);
    }

    public Pet pollAll(){
        if (!cats.isEmpty() && !dogs.isEmpty()){
            if (cats.peek().getOrder() > dogs.peek().getOrder()){
                return cats.poll().getPet();
            }else if(!cat.isEmpty()){
                return cats.poll().getPet();
            }else if(!dogs.isEmpty()){
                return dogs.poll().getPet();
            }else{
                throw new RuntimeException("err, no pet!!!")
            }
        }
    }

    public Cat pollCat(){
        if(!cat.isEmpty()){
                return cats.poll().getPet();
        }
        throw new RuntimeException("err, not cat")
    }
    // 余下省略...
}

  public static void sortStackByStack(Stack<Integer> stack) {
    Stack<Integer> help = new Stack<>();
    while (!stack.isEmpty()) {
      Integer cur = stack.pop();
      while (!help.isEmpty() && help.peek() < cur) {
        stack.push(help.pop());
      }
      help.push(cur);
    }

    while (!help.isEmpty()) {
      stack.push(help.pop());
    }
  }

  public static int[] getMaxWindow(int[] arr, int w) {
    if (arr == null || w < 1 || arr.length < w) {
      return null;
    }
    LinkedList<Integer> qmax = new LinkedList<>();
    int[] res = new int[arr.length - w + 1];
    int index = 0;
    for (int i = 0; i < arr.length; i++) {
      while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
        qmax.pollLast();
      }
      qmax.addLast(i);
      if ((qmax.peekFirst() == i - w)) {
        qmax.pollFirst();
      }
      if (i >= w - 1) {
        res[index++] = arr[qmax.peekFirst()];
      }
    }
    return res;
  }

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

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

public boolean isPalindrome(Node head){
    /** 第一步，找到中间节点，切分为左右两半*/
    Node n1 = head;
    Node n2 = head;

    while(n2.next != null && n2.next.next != null){
        n1 = n1.next;
        n2 = n2.next.next;
    }

    n2 = n1.next; // 右边第一个节点
    n1.next = null; // 最中间的节点（即左边的最后一个节点）的next设为null

    /** 第二步，反转右链表 */
    Node n3 = null;
    while(n2 != null){
        n3 = n2.next;
        n2.next = n1;
        n1 = n2;
        n2 = n3;
    }
    n3 = n1;

    /** 第三步，比较是否一致 */
    n2 = head;
    res = true;
    while(n1 != null && n2 != null){
        if (n1.value != n2.value){
            res = false;
            break;
        }
        n1 = n1.next;
        n2 = n2.next;
    }

    /** 第四步，还原链表 **/
    n1 = n3.next;
    n3 = null;
    while(n1 != null){
        n2 = n1.next;
        n1.next = n3;
        n3 = n1;
        n1 = n2;
    }

    return res;

}

public Node removeMidNode(Node head){
    if(head == null || head.next == null){
        return head;
    }
    if(head.next.next == null){
        return head.next;
    }
    Node n1 = head;
    Node n2 = head.next.next;

    while(n2.next != null && n2.next.next != null){
        n1 = n1.next;
        n2 = n2.next.next;
    }

    n1.next = n1.next.next;
    return head;
}