3.1 Describe how you could use a single array to implement three stacks.
Flexible Divisions的方案，当某个栈满了之后，需要把相邻的栈调整好，这是一个递归的过程。
每个stack有一些属性，所以不妨将每个stack封闭起来，我这里是用一个private的struct来实现，方便，同时对外部又不可见。
对于一些常用的操作，比如环形数组取下一个数，前一个数，都可以封装起来。
1 class XNStack { 2 public: 3 XNStack(int n, int capacity) : stackTotal(n), capacity(capacity), total(0) { 4 buff = new int[capacity]; 5 stacks = new XStackData[n]; 6 for (int i = 0; i < n; ++i) { 7 stacks[i].top = i * capacity / n; 8 stacks[i].capacity = capacity / n; 9 stacks[i].size = 0; 10 } 11 if (capacity % n) stacks[n - 1].capacity++; 12 } 13 14 ~XNStack() { 15 delete[] buff; 16 delete[] stacks; 17 } 18 19 void push(int stackNum, int v) { 20 cout << "push " << stackNum << " " << v << endl; 21 if (total >= capacity) { 22 cout << "full" << endl; 23 return; // full 24 } 25 total++; 26 if (stacks[stackNum].size < stacks[stackNum].capacity) { 27 buff[stacks[stackNum].top] = v; 28 stacks[stackNum].top = next(stacks[stackNum].top); 29 stacks[stackNum].size++; 30 } else { 31 int n = stackNum + 1; 32 if (n >= stackTotal) n = 0; 33 shift(n); 34 buff[stacks[stackNum].top] = v; 35 stacks[stackNum].top = next(stacks[stackNum].top); 36 stacks[stackNum].size++; 37 stacks[stackNum].capacity++; 38 } 39 } 40 41 void pop(int stackNum) { 42 cout << "pop " << stackNum << endl; 43 if (stacks[stackNum].size < 1) { 44 cout << "empty" << endl; 45 return; 46 } 47 total--; 48 stacks[stackNum].size--; 49 stacks[stackNum].top = pre(stacks[stackNum].top); 50 } 51 52 int top(int stackNum) { 53 return buff[pre(stacks[stackNum].top)]; 54 } 55 56 bool empty(int stackNum) const { 57 return stacks[stackNum].size == 0; 58 } 59 60 void print() { 61 for (int i = 0; i < stackTotal; ++i) { 62 cout << "stack[" << i << "]: size[" << stacks[i].size << "] capacity[" << stacks[i].capacity << "] top[" << stacks[i].top << "]" << endl; 63 } 64 65 for (int i = 0; i < capacity; ++i) { 66 cout << buff[i] << " "; 67 } 68 cout << endl; 69 } 70 71 private: 72 struct XStackData { 73 int top; 74 int capacity; 75 int size; 76 }; 77 78 int next(int i) { 79 i++; 80 if (i >= capacity) i = 0; 81 return i; 82 } 83 84 int pre(int i) { 85 i--; 86 if (i < 0) i = capacity - 1; 87 return i; 88 } 89 90 void shift(int stackNum) { 91 if (stacks[stackNum].size >= stacks[stackNum].capacity) { 92 int next = stackNum + 1; 93 if (next >= stackTotal) next = 0; 94 shift(next); 95 } else { 96 stacks[stackNum].capacity--; //最后一个移动的区间要把capacity减1，因为移动的空间就是由它来的 97 } 98 int j = stacks[stackNum].top; 99 for (int i = 0; i < stacks[stackNum].capacity; ++i) {100 int p = pre(j); 101 buff[j] = buff[p];102 j = p;103 }104 stacks[stackNum].top = next(stacks[stackNum].top);105 }106 int *buff;107 XStackData *stacks;108 int capacity;109 int total;110 int stackTotal;111 }; 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 UPImplement 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是它的子类。
1 class XStack { 2 public: 3 XStack(int capacity):capacity(capacity), t(0) { 4 buff = new int[capacity]; 5 } 6 7 ~XStack() { 8 delete[] buff; 9 } 10 11 void push(int v) { 12 if (t >= capacity) return; 13 buff[t++] = v; 14 } 15 16 void pop() { 17 if (t <= 0) return; 18 t--; 19 } 20 21 int top() { 22 if (t == 0) return 11111111; 23 return buff[t - 1]; 24 } 25 26 int size() const { 27 return t; 28 } 29 30 bool empty() const { 31 return t == 0; 32 } 33 34 void print() const { 35 for (int i = 0; i < t; ++i) { 36 cout << buff[i] << " "; 37 } 38 cout << endl; 39 } 40 private: 41 int *buff; 42 int capacity; 43 int t; 44 }; 45 46 // 3.2 47 class XMinStack: public XStack { 48 public: 49 50 XMinStack(int capacity):XStack(capacity), minStack(capacity) {} // should have a constructor 51 52 void push(int v) { 53 XStack::push(v); // call the superclass method 54 if (empty() || v < minStack.top()) { 55 minStack.push(v); 56 } 57 } 58 59 void pop() { 60 if (!empty() && !minStack.empty() && top() == minStack.top()) { 61 minStack.pop(); 62 } 63 XStack::pop(); 64 } 65 66 int min() { 67 if (minStack.empty()) return 111111; 68 return minStack.top(); 69 } 70 private: 71 XStack minStack; 72 }; 73 74 // 3.4 75 class Tower : public XStack { 76 public: 77 Tower():XStack(100) {} // constructor!! 78 }; 79 80 // 3.4 move 1...n from t1 to t3, t2 is cache 81 void moveDisk(int n, Tower &t1, Tower &t2, Tower &t3) { 82 if (n <= 0) return; 83 moveDisk(n - 1, t1, t3, t2); // t2 is destination here 84 t3.push(t1.top()); 85 t1.pop(); 86 moveDisk(n - 1, t2, t1, t3); // t2 is origin here 87 } 88 89 class XQueue { 90 public: 91 XQueue(int capacity):in(capacity), out(capacity) { 92 } 93 94 void enqueue(int v) { 95 in.push(v); 96 } 97 98 int dequeue() { 99 int v = front();100 out.pop();101 return v;102 }103 104 int front() {105 if (out.empty()) {106 while (!in.empty()) {107 out.push(in.top());108 in.pop();109 }110 }111 int v = out.top();112 return v;113 }114 private:115 XStack in;116 XStack out;117 };118 119 // 3.6, insertion sort120 void sort(XStack &st) {121 XStack tmp(st.size());122 while (!st.empty()) {123 /*if (tmp.empty() || st.top() <= tmp.top()) { // this part is not necessary 124 tmp.push(st.top());125 st.pop();126 } else { */127 int t = st.top();128 st.pop();129 while (!tmp.empty() && tmp.top() < t) {130 st.push(tmp.top());131 tmp.pop();132 }133 tmp.push(t);134 //}135 }136 137 while (!tmp.empty()) {138 st.push(tmp.top());139 tmp.pop();140 }141 }142 143 // 3.7 144 class Animal { // abstract class145 public: 146 Animal(int type):type(type) {}147 virtual ~Animal() = 0; // pure virtual148 int getOrder() const { return order; }149 void setOrder(int order) { this->order = order;}150 int getType() const { return type; }151 enum {CAT = 0, DOG = 1};152 private:153 int order;154 int type;155 };156 157 Animal::~Animal() {} // !!!! without this, link error occur158 159 class Dog : public Animal {160 public:161 Dog():Animal(Animal::DOG) {}162 ~Dog() {}163 };164 165 class Cat : public Animal {166 public:167 Cat():Animal(Animal::CAT) {} 168 ~Cat() {}169 };170 171 class AnimalQueue {172 public:173 AnimalQueue():order(0) {}174 175 void enqueue(Animal* a) {176 a->setOrder(order++);177 if (a->getType() == Animal::CAT) cats.push_back((Cat*)a); 178 else if (a->getType() == Animal::DOG) dogs.push_back((Dog*)a); 179 }180 181 Animal* dequeueAny() {182 Animal* cat = cats.empty() ? NULL : cats.front(); //when empty183 Animal* dog = dogs.empty() ? NULL : dogs.front();184 185 if (dog == NULL || (cat != NULL && cat->getOrder() < dog->getOrder())) {186 cats.pop_front();187 return cat;188 } else {189 dogs.pop_front();190 return dog;191 }192 }193 194 Dog* dequeueDog() {195 if (dogs.empty()) return NULL;196 Dog* dog = dogs.front();197 dogs.pop_front();198 return dog;199 }200 201 Cat* dequeueCat() {202 if (cats.empty()) return NULL;203 Cat* cat = cats.front();204 cats.pop_front();205 return cat;206 }207 208 bool empty() const {209 return cats.empty() && dogs.empty();210 }211 private:212 int order;213 list cats;214 list dogs;215 };