Animal.java

import java.util.Date;

public class Animal{
	String type;
	Date arrived;

}

Cat.java

public class Cat extends Animal{
	String name;
	public Cat(String name){
		super();
		this.name = name;
		type = "Cat";
	}
}

cc150_3_7.java

package cc150_3_7;

import java.util.Date;
import java.util.LinkedList;
import java.util.Queue;


public class AnimalShelter {
	
    private Queue<Cat> cats;
    private Queue<Dog> dogs;
	
    public AnimalShelter(){
        cats = new LinkedList<Cat>();
        dogs = new LinkedList<Dog>();
    }
    
    public void enqueue(Animal animal) throws Exception{
        boolean isCat = animal.type.equals("Cat");
        boolean isDog = animal.type.equals("Dog");
        if(!isCat && !isDog)
            throw new Exception("Unknow type of animal!");
        
        animal.arrived = new Date();
        if(isCat) 
        	{cats.offer((Cat) animal);
        	
        	}
        else {
        	dogs.offer((Dog) animal);
        }
        
    }
    
    public Animal dequeue() throws Exception{
    	boolean hasnocat = cats.isEmpty();
    	boolean hasnodog = dogs.isEmpty();
    	
    	if(hasnocat && hasnodog) throw new Exception("There are no animal");
    	
    	if(hasnodog) return cats.poll();
    	if(hasnocat) return dogs.poll();
    	
    	Cat temp_cat = cats.poll();
    	Dog temp_dog = dogs.poll();
    	if(temp_cat.arrived.before(temp_dog.arrived)){
    		dogs.offer(temp_dog);
    		return temp_cat;
    	}
    	else{
    		cats.offer(temp_cat);
    		return temp_dog;
    	}
    }
    
    public Cat dequeueCat() throws Exception{
    	if(cats.isEmpty()) throw new Exception("There is no Cat");
    	return cats.poll();
    }
    public Dog dequeueDog() throws Exception{
    	if(dogs.isEmpty()) throw new Exception("There is no Dog");
    	return dogs.poll();
    }
	
    
    public static void main(String[] args) throws Exception {
    	AnimalShelter test = new AnimalShelter();
    	Cat c1 = new Cat("c1");
    	Cat c2= new Cat("c2");
    	Cat c3 = new Cat("c3");
    	Cat c4= new Cat("c4");
    	
    	Dog d1 = new Dog("d1");
    	Dog d2= new Dog("d2");
    	Dog d3 = new Dog("d3");
    	Dog d4= new Dog("d4");
    	

    	test.enqueue(c4);
    	test.enqueue(d2);
    	test.enqueue(c2);
    	test.enqueue(d4);
    	test.enqueue(d3);
    	test.enqueue(c3);
    	test.enqueue(c1);
    	
    	
    	
    	System.out.println(test.dequeue().type);
    	System.out.println(test.dequeueCat().name);
    	System.out.println(test.dequeueDog().name);
    	
    	
    	
    }


}

Dog.java

public class Dog extends Animal{
	String name;
	public Dog(String name){
		super();
		this.name = name;
		type = "Dog";
	}
}