Animal shelter simulation using Queues

This is of one the interesting problems I've solved:


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.

My algorithm:

• Maintain two Queues, CatQ and a DogQ.

• If the user wants a Cat, dequeue from the CatQ, and if he wants a Dog, dequeue from DogQ.

• The problem gets trickier for dequeueAny, since there are two Queues and should be served on FIFO basis. While enqueuing, I'm inserting the arrivalTime too, so whichever animal has the lowestarrivalTime will be dequeued first.

Implementation:

```
static class Node{
Node next;
T type;
String animalName;
int arrivalTime;
Node(String name){
this.animalName = name;
}

@Override
public String toString(){
return this.animalName;
}
}

static class Dog{

}

static class Cat{

}

static class Queue{
Node front, rear;

public void enq(Node toEnq){
if(rear==null){
rear = toEnq;
front = rear;
}else{
rear.next = toEnq;
rear = rear.next;
}
}

public Node deq(){
if(front==null){
System.out.println("Underflow!");
return new Node("Error");
}else{
Node frn = front;
front = front.next;
return frn;
}
}

public void printQ(){
Node temp = front;
if(this.isEmpty()){
System.out.println("No animals here");
return;
}
while(temp.next!=null){
System.out.print(temp.animalName +

Structure

So your structure is definitely a bit off. First of all, you made your Node generic, which is good, as it could theoretically work with any content - which is what you want from a queue. But then, you have fields which just don't belong there, such as animalName (and type, which is just not needed).

So first of all, lets move animalName outside of the node and into the animal classes, where it belongs.

As cats and dogs are both animals, lets also create an Animal class which both extend:

static class Dog extends Animal {
    public Dog(String name) {
        super(name);
    }
}

static class Cat extends Animal {
    public Cat(String name) {
        super(name);
    }
}

static class Animal {
    String animalName;

    public Animal(String name) {
        this.animalName = name;
    }

    @Override
    public String toString() {
        return this.animalName;
    }
}

Now our Node class makes more sense (we'll remove arrivalTime later as well):

static class Node{
    Node next;
    int arrivalTime;
    T content;
    Node(T content){
        this.content = content;
    }

    @Override
    public String toString(){
        return this.content.toString();
    }
}

This restructuring did break some other parts of your code, but not that many. enq now doesn't work like this, so change it to:

public void enq(Node toEnq){
    toEnq.arrivalTime = this.arrivalTime;
    arrivalTime++;
    if (toEnq.content instanceof Cat) {
        catQ.enq(toEnq);
    } else {
        dogQ.enq(toEnq);
    }
}

Adding new animals is now simpler, and your queue is actually reusable, you can add anything:

myHouse.enq(new Node(new Cat("Bella")));

Misc

• fields should be private as to not expose implementation details

• you could easily get rid of the arrival time by just having one queue, and if deqAny is called, return the first entry, if deqDog or deqCat is called peek until you find the correct animal, then return that. (This would worsen your performance in some corner-cases, see comments.) A better idea would be to move arrivalTime into Animal, because it's a datapoint for animals, not for nodes. Ideally, you would also use some sort of time instead of a counter, because it makes more logical sense.

• don't shorten words in variable and method names, it makes code harder to read. Eg; printQ, what's a Q? deq? etc

• your whitespace usage is a bit off (spaces and vertical whitespace)

• an error node is not a good idea, nor is printing in a queue. just throw an exception, that way the code using your queue can decide how to handle that case.

• your AnimalHouse doesn't need to know about the implementation details of the queue. So remove the node fields (which aren't used anyways), and instead of passing and returning nodes, pass and return the content instead and create the nodes inside of the queues.

StackExchange Code Review Q#116642, answer score: 11