An animal shelter, which holds only dogs and cats, 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 Linked list data structure.
There are many approaches to solve this problem
1. We could maintain a single queue and keep inserting the element in the Queue. Using a single queue, dequeueAny is easy, but dequeueDog and dequeueCat would require iteration through the queue to find the first dog or cat. This would increase the complexity of the solution and decrease the efficiency.
2. An alternative approach that is simple, clean and efficient is to simply use separate queues for dogs and cats, and to place them within a wrapper class called an AnimalShelterQueue. We will store some sort of time stamp (insertion order) to mark when each animal was enqueued. When we call dequeueAny, will return the oldest of the tops of both the dog and cat queue. For operation dequeueDog and dequeueCat, we will return the top of respective queue.
package com.algorithmforum.cci.stack;
import java.util.EmptyStackException;
import java.util.LinkedList;
import java.util.Queue;
abstract class Animal {
private String name;
private int order;
public Animal(String name) {
this.name = name;
}
public int getOrder() {
return order;
}
public void setOrder(int order) {
this.order = order;
}
public String getName() {
return name;
}
/**
* Inserting the element with Order and incrementing the order by one for every new element.
* Latest element will maintain the largest value of the Order.
*
* @param animal
* @return boolean value
*/
public boolean isOlderThan(Animal animal) {
return this.order < animal.getOrder();
}
}
class Dog extends Animal {
public Dog(String name) {
super(name);
}
@Override
public String toString() {
return "Dog Name: " + this.getName();
}
}
class Cat extends Animal {
public Cat(String name) {
super(name);
}
@Override
public String toString() {
return "Cat Name: " + this.getName();
}
}
/**
* A clean and efficient approach to maintaining separate queues for dogs and cats,
* and to place them within a wrapper class called An AnimalShelterStack.
*
* We then store some sort of time stamp(insertion order) to mark when each animal was enqueued.
* When we call dequeueAny, will return the oldest of the tops of both the dog
* and cat queue.
* @author rajesh.kumar
* @since Aug 13, 2018 11:22:56 AM
*/
public class AnimalShelterQueue {
private Queue dogs;
private Queue cats;
private int order;
public AnimalShelterQueue() {
this.order = 0;
this.dogs = new LinkedList<>();
this.cats = new LinkedList<>();
}
/**
* dequeueAny cases:
* #1: if both stacks are empty, throw exception as no Animal will found.
* #2: if dogs stack is empty, return top from the cats stack.
* #3: if cats stack is empty, return top from the dogs stack.
* #4: if cats & dogs contains element, return older of top of both stack.
* @return
*/
public Animal dequeueAny() {
System.out.println("------------------dequeueAny------------------");
if (dogs.isEmpty() && cats.isEmpty()) {
throw new EmptyStackException();
} else if (dogs.isEmpty()) {
return dequeueCat();
} else if (cats.isEmpty()) {
return dequeueDog();
}
/**
* Look at top of dog and cat queues, and pop the queue with the oldest value.
*/
Animal dog = dogs.peek();
Animal cat = cats.peek();
boolean isDog = dog.isOlderThan(cat);
if (isDog) {
return dequeueDog();
} else {
return dequeueCat();
}
}
/**
* Check the type of Animal instance and insert in respective 'stack'.
* @param animal
* @return boolean
*/
public boolean enqueue(Animal animal) {
/**
* order is used as a sort of time stamp.
* It can be used to compare the insertion order of a dog to a cat.
**/
animal.setOrder(order++);
if (animal instanceof Cat) {
return cats.add((Cat) animal);
} else {
return dogs.add((Dog) animal);
}
}
/**
* Return the top of dogs Queue.
* @return animal
*/
public Animal dequeueDog() {
System.out.println("------------------dequeueDog------------------");
return dogs.poll();
}
/**
* Return the top of cats Queue.
* @return animal
*/
public Animal dequeueCat() {
System.out.println("------------------dequeueCat------------------");
return cats.poll();
}
/**
* Test the queue.
* @param args
*/
public static void main(String[] args) {
AnimalShelterQueue queue = new AnimalShelterQueue();
queue.enqueue(new Dog("dog1"));
queue.enqueue(new Cat("cat1"));
queue.enqueue(new Cat("cat2"));
queue.enqueue(new Dog("dog2"));
queue.enqueue(new Cat("cat2"));
queue.enqueue(new Dog("dog3"));
// Should print 'cat1' as it was the first cat entered in Shelter.
System.out.println(queue.dequeueCat());
// Should print dog1 as it was the first animal entered in Shelter.
System.out.println(queue.dequeueAny());
// Should print cat1 as it is the only cat in the Shelter.
System.out.println(queue.dequeueDog());
}
}
OUTPUT:
------------------dequeueCat------------------
Cat Name: cat1
------------------dequeueAny------------------
------------------dequeueDog------------------
Dog Name: dog1
------------------dequeueDog------------------
Dog Name: dog2
I admire this article for the well-researched content and excellent wording. I got so involved in this material that I couldn’t stop reading. I am impressed with your work and skill. Thank you so much. last shelter survival tips
ReplyDeleteSuccessful alternatives to the use and abuse of animals will in time make the old and cruel customs obsolete and offer a happier future for our fellow creatures. We need to succeed in our effort to redress attitudes that have allowed many millions of animals' lives to have been sacrificed. And then, as humans we may be able to hold up our heads, knowing we are indeed becoming humane. elevage-oie-tricard
ReplyDeletecool
ReplyDeleteAsking how to advocate for the ethical treatment of animals is the first step in the process. It shows that you care about the ethical treatment of pets and other animals. You think that ethics forms the root of your concern. When you see a person in Hawaii throw six fragile kittens off a cliff (fact), you overflow with a brew of grief and anger. When you read of inhumane persons stalking powerful elephants to steal their tusks/teeth (fact), you boil with hot indignation. Seeing, reading, and hearing of such abuse makes you resolve to take meaningful action, and you set out to learn how to advocate for the ethical treatment of animals. dog breeder
ReplyDeleteSuper-Duper site! I am Loving it!! Will come back again, Im taking your feed also, Thanks. macaw for sale
ReplyDeleteReally i am impressed from this post....the person who create this post it was a great human..thanks for shared this with us. Visa US dị n'ịntanetị
ReplyDelete