# Animal Shelter

`Design`, `Queue`,

Hard

## Question

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.

Example

``````int CAT = 0
int DOG = 1

enqueue("james", DOG);
enqueue("tom", DOG);
enqueue("mimi", CAT);
dequeueAny();  // should return "james"
dequeueCat();  // should return "mimi"
dequeueDog();  // should return "tom"``````

Challenge

Can you do it with single Queue?

## Analysis

### Single Queue

challenge里所说的Single Queue的方法，难点在于shift queue，因为不能用两个queue分别来track同一个type中的先后顺序，那么就需要用shift的方式来维持队列。找到对应的type，记录shift的次数，这样poll了之后，要再shift总长减去之前shift的次数，来还原queue的状态。相应的dequeue算法复杂度也高很多O(n)

## Solution

### Two Queues

``````class Node {
int time;
String name;

Node(String name, int time) {
this.name = name;
this.time = time;
}
public String getName() {
return this.name;
}
public int getTime() {
return this.time;
}
}

public class AnimalShelter {

private static final int DOG = 1;
private static final int CAT = 0;

private int tot;

public AnimalShelter() {
// do initialize if necessary
tot = 0;
}

/**
* @param name a string
* @param type an integer, 1 if Animal is dog or 0
* @return void
*/
void enqueue(String name, int type) {
tot += 1;
if (type == DOG) {
} else {
}
}

public String dequeueAny() {
if (cats.isEmpty()) {
return dequeueDog();
} else if (dogs.isEmpty()) {
return dequeueCat();
} else {
int dogTime = dogs.getFirst().getTime();
int catTime = cats.getFirst().getTime();
if (catTime < dogTime) {
return dequeueCat();
} else {
return dequeueDog();
}
}
}

public String dequeueDog() {
String name = dogs.getFirst().getName();
dogs.removeFirst();
return name;
}

public String dequeueCat() {
String name = cats.getFirst().getName();
cats.removeFirst();
return name;
}
}``````

### Single Queue

``````class Node {
String name;
int type;
Node(String name, int type) {
this.name = name;
this.type = type;
}
}
public class AnimalShelter {
Queue<Node> queue;
public AnimalShelter() {
// do initialize if necessary
}

/**
* @param name a string
* @param type an integer, 1 if Animal is dog or 0
* @return void
*/
void enqueue(String name, int type) {
queue.offer(new Node(name, type));
}

public String dequeueAny() {
Node node = queue.poll();
return node.name;
}

public String dequeueDog() {
return dequeueType(1);
}

public String dequeueCat() {
return dequeueType(0);
}

private String dequeueType(int type) {
int shiftTime = 0;
while (queue.peek().type != type) {
queue.offer(queue.poll());
shiftTime++;
}
Node node = queue.poll();
shiftTime = queue.size() - shiftTime;
while (shiftTime != 0) {
queue.offer(queue.poll());
shiftTime--;
}
return node.name;
}
}``````

Last updated