Animal Shelter

An animal shelter, which holds only dogs and cats, operates on a strictly “first in, first out” basis. People must adopt either the “oldest” of all animals, or they can select whether they would prefer the oldest dog, or oldest cat. Create the data structures to maintain this system and implement operations such as enqueue, dequeue_any, dequeue_dog and dequeue_cat.

Solution

We can use two queues to solve this problem - one queue for cats, and another for dogs. When we enqueue an animal, we will include a timestamp to indicate when the animal was added to the queue. In order to implement the dequeue_dog and dequeue_cat methods, we will use a simple dequeue from the appropriate stack. To implement the dequeue_any method, we will compare the timestamp of the first record in the cat and dog queue, and select the element which has the oldest timestamp.

class Node:
  def __init__(self, value):
    self.value = value
    self.timestamp = time.time()
    self.next = None

class Queue:
  def __init__(self):
    self.first = None
    self.last = None

  def enqueue(self, value):
    if(self.first == None):
      node = Node(value)
      self.first = node
      self.last = node

    else:
      node = Node(value)
      node.next = self.first
      self.last.next = node
      self.last = node

  def is_empty(self):
    return self.first == None

  def peek_time(self):
    return self.first.timestamp

  def dequeue(self):
    if(self.is_empty()):
      return None
    else:
      value = self.first.value
      self.first = self.first.next
      return value

class AnimalQueue:
  def __init__(self):
    self.cats = Queue()
    self.dogs = Queue()

  def enqueue(self, value, type):
    if(type == 'cat'):
      self.cats.enqueue(value)
    elif(type == 'dog'):
      self.dogs.enqueue(value)

  def dequeue_cat(self):
    return self.cats.dequeue()

  def dequeue_dog(self):
    return self.dogs.dequeue()

  def dequeue_any(self):
    if(self.cats.peek_time() < self.dogs.peek_time()):
      return self.cats.dequeue()
    elif(self.dogs.peek_time() < self.cats.peek_time()):
      return self.dogs.dequeue()