Cranking the Coding Interview: Stacks and Queues

• Animal Shelter
• Queue via Stacks
• Three in One

Animal Shelter

這道題目就是使用deque再合适不過了。

不過deque的實作可以使用list來實作，這裡實作的方法就是開頭一個指針指向開頭、一個指向結尾。

用開頭的指針來做被收養的操作，如果不是符合要求的話，那麼就建立一個list存儲需要的内容。然後需要往收容所增加動物的時候，就把動物加在連結清單的後面。

具體代碼實作：

class CatDogAsylum {
public:
    vector<int> asylum(vector<vector<int> > ope) {
        // write code here
        deque<int> que;
        vector<int> seq;

        int ope_size = ope.size();
        for(int i = ; i < ope_size; i++) {
            // put animal into shelter
            if(ope[i][] == ) {
                que.push_back(ope[i][]);
            }
            // adopt anmial 
            else {
                vector<int> pre;
                if(ope[i][] == ) {
                    seq.push_back(que.front());
                    que.pop_front();
                }
                else {
                    // adopt dog
                    if(ope[i][] == ) {
                        while(!que.empty()) {
                            int tp = que.front();
                            if(tp > ) { seq.push_back(tp); que.pop_front(); break; }
                            else { que.pop_front(); pre.push_back(tp); } 
                        }   
                        if(!pre.empty()) que.insert(que.begin(), pre.begin(), pre.end());
                    } 
                    // adopt cat
                    else {
                        while(!que.empty()) {
                            int tp = que.front();
                            if(tp < ) { seq.push_back(tp); que.pop_front(); break; }
                            else { que.pop_front(); pre.push_back(tp); } 
                        }   
                        if(!pre.empty()) que.insert(que.begin(), pre.begin(), pre.end());                       
                    }
                }
            }
        }
        return seq;
    }
};
           

在cc189上的代碼如下：

abstract class Animal {
    private int order;
    protected String name;
    public Animal(String n) {name = n;}
    public int getOrder() {return order;}
    public boolean isOrderThan(Animal a) {
        return this.order < a.getOrder();
    }
};

class AnimalQueue{
    LinkedList<Dog> dogs = new LinkedList<Dog>();
    LinkedList<Cat> cats = new LinkedList<Cats>();
    private int oreder = ;

    public void enqueue(Animal a) {
        a.setOrder(order);
        order++;
    }

    public Animal dequeueAny() {
        if(dogs.size() == ) {
            return dequeueCats();
        }
        if(cats.size() == ) {
            return dequeueDogs();
        }
        Dog dog = dog.peek();
        Cat cat = cats.peek();
        if(dog.isOrderThan(cat)) return deuqueDogs();
        else return dequeueCats();
    } 

    public Dog dequeueDogs() {
        return dogs.poll();
    }

    public Cat dequeueCats() {
        return cats.poll();
    } 
}

public class Dog extend Animal {
    public Dog(String n) {super(n);}
}

public class Cat extend Animal {
    public Cat(String n) {super(n);}
}
           

Queue via Stacks

這裡做的就是把兩個棧實作為隊列，我的方法比較簡單，就是使用一個棧來存資料，另外一個棧用來做中轉。那麼就可以寫成：

class Solution
{
public:
    void push(int node) {
        if(!stack1.empty()) {
            int tmp;
            while(!stack1.empty()) {
                tmp = stack1.top();
                stack1.pop();
                stack2.push(tmp);
            }
            stack1.push(node);
            while(!stack2.empty()) {
                tmp = stack2.top();
                stack2.pop();
                stack1.push(tmp);
            }
        }   
        else stack1.push(node);
    }

    int pop() {
        if(!stack1.empty()) {int res = stack1.top(); stack1.pop(); return res;}
        else return ;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};
           

Three in One