Animal Shelter 230

Question

An animal shelter holds only dogs and cats, and operates on a strictly "first in, first out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog and dequeueCat.

Example

int CAT = 0

int DOG = 1

enqueue("james", DOG);

enqueue("tom", DOG);

enqueue("mimi", CAT);

dequeueAny(); // should return "james"

dequeueCat(); // should return "mimi"

dequeueDog(); // should return "tom"

Challenge

Can you do it with single Queue?

Solution

用两个queue分别存dog和cat，每个animal除了名字和类别外，还有一个time属性，以此来决定dequeueAny()的时候的出栈元素。

如果只用一个queue，需要用到循环队列的思想。将所有animal存在一个queue中，出队时，在找到第一个符合要求的出队元素之前，出队的元素全部从队尾再次入队，在找到第一个符合要求的元素后，再将剩下的元素依次出队之后再入队。

代码如下：

2 Queues

public class test {
    class Animal{
        String name;
        int type;
        int time;
        public Animal(String name, int type, int time){
            this.name = name;
            this.type = type;
            this.time = time;
        }
    }

    Queue<Animal> Cat = new LinkedList<Animal>();
    Queue<Animal> Dog = new LinkedList<Animal>();
    int time = 0;

    public static void main(String[] args){
        test t = new test();
        t.enqueue("james", 1);
        t.enqueue("tom", 1);
        t.enqueue("mimi", 0);
        System.out.println(t.dequeueAny());  // should return "james"
        System.out.println(t.dequeueCat());  // should return "mimi"
        System.out.println(t.dequeueDog());  // should return "tom"
    }

    private void enqueue(String name, int type){
        if(type == 0){
            Cat.offer(new Animal(name, type, time));
        }else{
            Dog.offer(new Animal(name, type, time));
        }
        time++;
    }

    private String dequeueAny(){
        Animal catOldest = Cat.peek();
        Animal dogOldest = Dog.peek();
        if(catOldest.time < dogOldest.time){
            return Cat.poll().name;
        }else{
            return Dog.poll().name;
        }
    }

    private String dequeueCat(){
        return Cat.poll().name;
    }

    private String dequeueDog(){
        return Dog.poll().name;
    }
}

1 Queue

public class test {
    class Animal{
        String name;
        int type;
        public Animal(String name, int type){
            this.name = name;
            this.type = type;
        }
    }

    Queue<Animal> queue = new LinkedList<Animal>();

    public static void main(String[] args){
        test t = new test();
        t.enqueue("james", 1);
        t.enqueue("tom", 1);
        t.enqueue("mimi", 0);
        System.out.println(t.dequeueAny());  // should return "james"
        System.out.println(t.dequeueCat());  // should return "mimi"
        System.out.println(t.dequeueDog());  // should return "tom"
    }

    private void enqueue(String name, int type){
        queue.offer(new Animal(name, type));
    }

    private String dequeueAny(){
        return queue.poll().name;
    }

    private String dequeueCat(){
        return dequeueType(0);
    }

    private String dequeueDog(){
        return dequeueType(1);
    }

    private String dequeueType(int type){
        int shiftNumber = 0;
        while(queue.peek().type != type){
            queue.offer(queue.poll());
            shiftNumber++;
        }
        Animal target = queue.poll();
        shiftNumber = queue.size() - shiftNumber;
        while(shiftNumber != 0){
            queue.offer(queue.poll());
            shiftNumber--;
        }
        return target.name;
    }
}