Wednesday, 15 August 2018
Monday, 13 August 2018
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.