Careercup | Chapter 3

3.1 Describe how you could use a single array to implement three stacks.

Flexible Divisions的方案，当某个栈满了之后，需要把相邻的栈调整好，这是一个递归的过程。

每个stack有一些属性，所以不妨将每个stack封闭起来，我这里是用一个private的struct来实现，方便，同时对外部又不可见。

对于一些常用的操作，比如环形数组取下一个数，前一个数，都可以封装起来。

class XNStack {
public:
    XNStack(int n, int capacity) : stackTotal(n), capacity(capacity), total(0) {
        buff = new int[capacity];
        stacks = new XStackData[n];
        for (int i = 0; i < n; ++i) {
            stacks[i].top = i * capacity / n;
            stacks[i].capacity = capacity / n;
            stacks[i].size = 0;
        }
        if (capacity % n) stacks[n - 1].capacity++;
    }
    
    ~XNStack() {
        delete[] buff;
        delete[] stacks;
    }

    void push(int stackNum, int v) {
        cout << "push " << stackNum << " " << v << endl;
        if (total >= capacity) {
            cout << "full" << endl;
            return; // full
        }
        total++;
        if (stacks[stackNum].size < stacks[stackNum].capacity) {
            buff[stacks[stackNum].top] = v;
            stacks[stackNum].top = next(stacks[stackNum].top);
            stacks[stackNum].size++;
        } else {
            int n = stackNum + 1;
            if (n >= stackTotal) n = 0;
            shift(n);
            buff[stacks[stackNum].top] = v;
            stacks[stackNum].top = next(stacks[stackNum].top);
            stacks[stackNum].size++;
            stacks[stackNum].capacity++;
        }
    }

    void pop(int stackNum) {
        cout << "pop " << stackNum << endl;
        if (stacks[stackNum].size < 1) {
            cout << "empty" << endl;
            return;
        }
        total--;
        stacks[stackNum].size--;    
        stacks[stackNum].top = pre(stacks[stackNum].top);    
    }

    int top(int stackNum) {
        return buff[pre(stacks[stackNum].top)];
    }

    bool empty(int stackNum) const {
        return stacks[stackNum].size == 0;
    }

    void print() {
        for (int i = 0; i < stackTotal; ++i) {
            cout << "stack[" << i << "]: size[" << stacks[i].size << "] capacity[" << stacks[i].capacity << "] top[" << stacks[i].top << "]" << endl;
        }

        for (int i = 0; i < capacity; ++i) {
            cout << buff[i] << " ";
        }
        cout << endl;
    }

private:
    struct XStackData {
        int top;
        int capacity;
        int size;
    };
    
    int next(int i) {
        i++;
        if (i >= capacity) i = 0;
        return i;
    }

    int pre(int i) {
        i--;
        if (i < 0) i = capacity - 1;
        return i;
    }

    void shift(int stackNum) {
        if (stacks[stackNum].size >= stacks[stackNum].capacity) {
            int next = stackNum + 1;
            if (next >= stackTotal) next = 0;
            shift(next);
        } else {
            stacks[stackNum].capacity--; //最后一个移动的区间要把capacity减1，因为移动的空间就是由它来的
        }
        int j = stacks[stackNum].top;
        for (int i = 0; i < stacks[stackNum].capacity; ++i) {
            int p = pre(j); 
            buff[j] = buff[p];
            j = p;
        }
        stacks[stackNum].top = next(stacks[stackNum].top);
    }
    int *buff;
    XStackData *stacks;
    int capacity;
    int total;
    int stackTotal;
};

3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in 0(1) time.

两个栈。

3.3 Imagine a (literal) stack of plates. If the stack gets too high, it migh t topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop () should behave identically to a single stack (that is, pop () should return the same values as it would if there were just a single stack).
FOLLOW UP
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

把3.1 改一改就好了。这样在实现确保每个stack是full就比较简单了，只需要修改top指针，不需要真正地搬动。当然careercup里面的解法也是对的。

3.4 In the classic problem of the Towers of Hanoi, you have 3 towers and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (i.e., each disk sits on top of an even larger one). You have the following constraints:
(T) Only one disk can be moved at a time.
(2) A disk is slid off the top of one tower onto the next rod.
(3) A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first tower to the last using Stacks.

汉诺塔。经典递归问题。

3.5 Implement a MyQueue class which implements a queue using two stacks.

两个栈，一个用来进队列，一个用来出队列。

3.6 Write a program to sort a stack in ascending order (with biggest items on top). You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek, and isEmpty.

插入排序。使得缓存栈是从栈顶到栈底递增，最后再把缓存栈的东西倒到原来的栈中。注意代码重构。

3.7 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. You may use the built-in L inkedL ist data structure.

感觉career cup的题虽然简单些，但是可以检查你的代码简洁功力，还有OO design的功力。

纯虚的析构函数是需要一个实现体的，不然通不过编译，link error。

设计方面，animal必须是抽象类，dog和cat是它的子类。

class XStack {
public: 
    XStack(int capacity):capacity(capacity), t(0) {
        buff = new int[capacity];
    }

    ~XStack() {
        delete[] buff;
    }

    void push(int v) {
        if (t >= capacity) return;
        buff[t++] = v;
    }

    void pop() {
        if (t <= 0) return;
        t--;
    }

    int top() {
        if (t == 0) return 11111111;
        return buff[t - 1];
    }

    int size() const {
        return t;
    }
    
    bool empty() const {
        return t == 0;
    }

    void print() const {
        for (int i = 0; i < t; ++i) {
            cout << buff[i] << " ";
        }
        cout << endl;
    }
private:
    int *buff;
    int capacity;
    int t;
};

// 3.2
class XMinStack: public XStack {
public:

    XMinStack(int capacity):XStack(capacity), minStack(capacity) {} // should have a constructor

    void push(int v) {
        XStack::push(v); // call the superclass method
        if (empty() || v < minStack.top()) {
            minStack.push(v);
        }
    }

    void pop() {
        if (!empty() && !minStack.empty() && top() == minStack.top()) {
            minStack.pop();
        }
        XStack::pop();
    }

    int min() {
        if (minStack.empty()) return 111111;
        return minStack.top();
    }
private:
    XStack minStack;
};

// 3.4
class Tower : public XStack {
public:
    Tower():XStack(100) {} // constructor!!
};

// 3.4 move 1...n from t1 to t3, t2 is cache
void moveDisk(int n, Tower &t1, Tower &t2, Tower &t3) {
    if (n <= 0) return;
    moveDisk(n - 1, t1, t3, t2); // t2 is destination here
    t3.push(t1.top());
    t1.pop();
    moveDisk(n - 1, t2, t1, t3); // t2 is origin here
}

class XQueue {
public:
    XQueue(int capacity):in(capacity), out(capacity) {
    }

    void enqueue(int v) {
        in.push(v);
    }

    int dequeue() {
        int v = front();
        out.pop();
        return v;
    }

    int front() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
        int v = out.top();
        return v;
    }
private:
    XStack in;
    XStack out;
};

// 3.6, insertion sort
void sort(XStack &st) {
     XStack tmp(st.size());
     while (!st.empty()) {
         /*if (tmp.empty() || st.top() <= tmp.top()) { // this part is not necessary 
             tmp.push(st.top());
             st.pop();
         } else { */
         int t = st.top();
         st.pop();
         while (!tmp.empty() && tmp.top() < t) {
             st.push(tmp.top());
             tmp.pop();
         }
         tmp.push(t);
         //}
     }

     while (!tmp.empty()) {
         st.push(tmp.top());
         tmp.pop();
     }
}

// 3.7 
class Animal { // abstract class
public: 
    Animal(int type):type(type) {}
    virtual ~Animal() = 0; // pure virtual
    int getOrder() const { return order; }
    void setOrder(int order) {this->order = order;}
    int getType() const { return type; }
    enum {CAT = 0, DOG = 1};
private:
    int order;
    int type;
};

Animal::~Animal() {} // !!!! without this, link error occur

class Dog : public Animal {
public:
    Dog():Animal(Animal::DOG) {}
    ~Dog() {}
};

class Cat : public Animal {
public:
    Cat():Animal(Animal::CAT) {} 
    ~Cat() {}
};

class AnimalQueue {
public:
    AnimalQueue():order(0) {}

    void enqueue(Animal* a) {
        a->setOrder(order++);
        if (a->getType() == Animal::CAT) cats.push_back((Cat*)a); 
        else if (a->getType() == Animal::DOG) dogs.push_back((Dog*)a); 
    }

    Animal* dequeueAny() {
        Animal* cat = cats.empty() ? NULL : cats.front(); //when empty
        Animal* dog = dogs.empty() ? NULL : dogs.front();
        
        if (dog == NULL || (cat != NULL && cat->getOrder() < dog->getOrder())) {
            cats.pop_front();
            return cat;
        } else {
            dogs.pop_front();
            return dog;
        }
    }

    Dog* dequeueDog() {
        if (dogs.empty()) return NULL;
        Dog* dog = dogs.front();
        dogs.pop_front();
        return dog;
    }

    Cat* dequeueCat() {
        if (cats.empty()) return NULL;
        Cat* cat = cats.front();
        cats.pop_front();
        return cat;
    }

    bool empty() const {
        return cats.empty() && dogs.empty();
    }
private:
    int order;
    list<Cat*> cats;
    list<Dog*> dogs;
};