Question3_7.java

import java.util.LinkedList;

/**
 * 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.
 * You may use the built-in LinkedList data structure.
 * 
 * Time  Complexity: O(1)
 * Space Complexity: O(n)
 */

public class Question3_7 {
    private LinkedList<Animal> cats;
    private LinkedList<Animal> dogs;
    private int timestamp;
    
    public Question3_7() {
        cats = new LinkedList<Animal>();
        dogs = new LinkedList<Animal>();
        timestamp = 0;
    }
    
    public void enqueue(Animal animal) {
        animal.order = timestamp++;
        if (animal.type == Animal.Type.cat) {
            cats.addLast(animal);
        } else {
            dogs.addLast(animal);
        }
    }
    
    public Animal dequeueAny() {
        Animal cat = null;
        if (!cats.isEmpty()) {
            cat = cats.removeFirst();
        }
        
        Animal dog = null;
        if (!dogs.isEmpty()) {
            dog = dogs.removeFirst();
        }
        
        if (cat == null) {
            return dog;
        }
        
        if (dog == null) {
            return cat;
        }
        
        if (cat.order > dog.order) {
            cats.addFirst(cat);
            return dog;
        } else {
            dogs.addFirst(dog);
            return cat;
        }
    }
    
    public Animal dequeueDog() {
        Animal dog = null;
        if (!dogs.isEmpty()) {
            dog = dogs.removeFirst();
        }
        return dog;
    }
    
    public Animal dequeueCat() {
        Animal cat = null;
        if (!cats.isEmpty()) {
            cat = cats.removeFirst();
        }
        return cat;
    }
    
    
    public static void main(String[] args) {
        Question3_7 question3_7 = new Question3_7();
        int time = 0;
        for (int i = 0; i < 3; ++i) {
            Animal animal = new Animal(Animal.Type.dog, "dog" + time++);
            question3_7.enqueue(animal);
        }
        for (int i = 0; i < 4; ++i) {
            Animal animal = new Animal(Animal.Type.cat, "cat" + time++);
            question3_7.enqueue(animal);
        }
        for (int i = 0; i < 2; ++i) {
            Animal animal = new Animal(Animal.Type.dog, "dog" + time++);
            question3_7.enqueue(animal);
        }

        System.out.print(question3_7.dequeueCat().name + "\t");
        System.out.print(question3_7.dequeueDog().name + "\t");
        System.out.print(question3_7.dequeueAny().name + "\t");
        System.out.print(question3_7.dequeueAny().name + "\t");
        System.out.print(question3_7.dequeueCat().name + "\t");
        System.out.print(question3_7.dequeueAny().name + "\t");
        System.out.print(question3_7.dequeueDog().name + "\t");
        System.out.print(question3_7.dequeueCat().name + "\t");
        System.out.print(question3_7.dequeueAny().name + "\t");
        System.out.println();
        System.out.println();
        System.out.println("Expected Output:");
        System.out.println("cat3\tdog0\tdog1\tdog2\tcat4\tcat5\tdog7\tcat6\tdog8");
    }
}


class Animal {
    enum Type {dog, cat};
    Type type;
    String name;
    int order;
    
    public Animal(Type type, String name) {
        this.type = type;
        this.name = name;
    }
}