Animal Shelter (Ladder)

Description

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?

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   class AnimalNode {
   public:
    string name;
    int prior;
    AnimalNode(string _name, int _prior): name(_name), prior(_prior) {}
   };
   class AnimalShelter {
   public:
    AnimalShelter() {
        // do initialization if necessary
        time = 0;
    }
    /**
     * @param name a string
     * @param type an integer, 1 if Animal is dog or 0
     * @return void
     */
    void enqueue(string &name, int type) {
        // Write your code here
        if (type == 1) {
            qDog.push(AnimalNode(name, time));
        } else if (type == 0) {
            qCat.push(AnimalNode(name, time));
        }
        time++;
        return;
    }
    string dequeueAny() {
        // Write your code here
        if (!qCat.empty() && qDog.empty()) {
            return dequeueCat();
        } else if (qCat.empty() && !qDog.empty()) {
            return dequeueDog();
        } else if (!qCat.empty() && !qDog.empty()) {
            if (qCat.front().prior < qDog.front().prior) {
                return dequeueCat();
            } else {
                return dequeueDog();
            }
        }
        return {};
    }
    string dequeueDog() {
        // Write your code here
        string result;
        if (!qDog.empty()) {
            result = qDog.front().name;
            qDog.pop();
        }
        return result;
    }
    string dequeueCat() {
        // Write your code here
        string result;
        if (!qCat.empty()) {
            result = qCat.front().name;
            qCat.pop();
        }
        return result;
    }
   private:
    int time;
    queue<AnimalNode> qCat;
    queue<AnimalNode> qDog;
   };
   

Similar problems

x

Tags

x