栈和队列基础训练(二)

题目一：

　　请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。给定一个int[] numbers，其中第一个元素为栈顶，请返回排序后的栈。请注意这是一个栈，意味着排序过程中你只能访问到第一个元素。
　　测试样例：[1,2,3,4,5]  返回：[5,4,3,2,1]。

　　思路：这道题目很考验逻辑思维能力。将要排序的栈记为source,申请的辅助栈记为target。在source上执行pop操作，弹出的元素记为cru。   如果cru大于或等于target的栈顶元素，则将cru直接压入target。  如果cru小于target的栈顶元素，则将target的元素逐一弹出，逐一压入source，直到cru大于或等于target的栈顶元素，再将cru压入target。一直执行以上操作，直到source中的全部元素压入到target，最后返回target,完成排序。

import java.util.Stack;

public class StackSort {
    public static void main(String[] args) {
        StackSort obj = new StackSort();
        obj.twoStacksSort(new int[] { 8, 2, 3, 4, 5 });  // 输出 8 5 4 3 2
    }

    public void twoStacksSort(int[] numbers) {
        // 初始化原始栈
        Stack<Integer> source = new Stack<>();
        for (int i = numbers.length - 1; i >= 0; i--) {
            source.push(numbers[i]);
        }

        Stack<Integer> target = twoStacksSort(source);
        while (!target.isEmpty()) {
            System.out.println(target.pop());
        }
    }

    public Stack<Integer> twoStacksSort(Stack<Integer> source) {

        Stack<Integer> target = new Stack<>();
        sortToTarget(source, target);

        return target;
    }

    private void sortToTarget(Stack<Integer> source, Stack<Integer> target) {
        while (!source.empty()) {
            int v1 = source.pop(); // 揭开盖子
            if (target.empty()) {
                target.push(v1);
            } else {
                int v2 = target.peek();
                if (v1 >= v2) { // 盖子大，直接放入
                    target.push(v1);
                } else { // 盖子小，把大的先回收
                    source.push(target.pop());
                    // 直到有盖子的容身之所
                    while (!target.empty() && v1 < target.peek()) {
                        source.push(target.pop());
                    }
                    target.push(v1);
                }
            }
        }
    }
}

题目二：

　　猫狗收容所：有家动物收容所只收留猫和狗，但有特殊的收养规则，收养人有两种收养方式，第一种为直接收养所有动物中最早进入收容所的，第二种为选择收养的动物类型（猫或狗），并收养该种动物中最早进入收容所的。给定一个操作序列int[][2] 代表所有事件。若第一个元素为1，则代表有动物进入收容所，第二个元素为动物的编号，正数代表狗，负数代表猫；若第一个元素为2，则代表有人收养动物，第二个元素若为0，则采取第一种收养方式(最早)，若为1，则指定收养狗，若为-1则指定收养猫。请按顺序返回收养的序列。若出现不合法的操作，即没有可以符合领养要求的动物，则将这次领养操作忽略。

　　测试样例：[1, 1], [1, -1], [1, 0], [1, -5], [2, 0], [2, -1], [2, 0;  返回 [1, -1, -5]。

　　思路：可以根据题目要求画出下图所示的树。

　　　　

　　从题目中我们可以知道需要按照时间顺序求解出收养动物编号的序列，这里先进来的动物是最早可能被收养的，所以我们可以使用队列这种数据结构来存储其中的数据。我们可以使用两个队列，一个是猫的队列，一个是狗的队列这样可以方便我们入队和出队。这样的话当出队的时候就有一个问题，当第二个元素为0的时候就不知道该取谁了。我们可以利用一个全局变量来创建一个类似于时间点的东西，然后根据这个全局变量的大小判断谁先被收留，然后就可以选择谁先被收养了。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class CatDogAsylum {
    private static class Animal {
        int type;
        int time;
        static int timeline;// 全局变量，记录动物的时间点

        public Animal(int typeNumber) {
            this.type = typeNumber;
            this.time = timeline++;
        }
    }

    public ArrayList<Integer> asylum(int[][] ope) {
        ArrayList<Integer> res = new ArrayList<>();

        Queue<Animal> cats = new LinkedList<>();
        Queue<Animal> dogs = new LinkedList<>();
        for (int[] row : ope) {
            int op = row[0];
            int typeNumber = row[1];
            if (op == 1) {// 增加
                if (typeNumber > 0) {
                    dogs.add(new Animal(typeNumber));
                }
                if (typeNumber < 0) {
                    cats.add(new Animal(typeNumber));
                }
            } else if (op == 2) {// 减少
                if (typeNumber == 0) {// 从两个队列中选timeline最小的
                    if ((!dogs.isEmpty()) && (cats.isEmpty() || dogs.peek().time < cats.peek().time)) {
                        res.add(dogs.poll().type);
                    }
                    if ((!cats.isEmpty()) && (dogs.isEmpty() || dogs.peek().time > cats.peek().time)) {
                        res.add(cats.poll().type);
                    }
                } else {// 用户指定了类型
                    if (typeNumber == 1 && !dogs.isEmpty()) {
                        res.add(dogs.poll().type);
                    }
                    if (typeNumber == -1 && !cats.isEmpty()) {
                        res.add(cats.poll().type);
                    }
                }
            } else {
                break;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        CatDogAsylum obj = new CatDogAsylum();
        int[][] data = { { 1, 1 }, { 1, -1 }, { 1, 0 }, { 1, -5 }, { 2, 0 }, { 2, -1 }, { 2, 0 } };
        // 输出 [1, -1, -5]
        System.out.println(obj.asylum(data));
    }
}