像是夏日的最后一天
- to do
3.1】用一个数组实现三个栈
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 O(1) time.
3.3】设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。
3.4】汉诺塔问题, solve w/ stack
3.5] implement queue w/ 2 stacks
- easy, but consider optimization
- Min Stack
in reminder of typedef struct, init list
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
int min = s.empty()? x : std::min(x, s.top().min);
s.push(elem(x, min));
}
void pop() {
s.pop();
}
int top() {
return s.top().val;
}
int getMin() {
return s.top().min;
}
private:
typedef struct elem { // if skip `elem` here, would cause error when delcaring `elem()` constructor within body, cuz not declared yet technically
int val;
int min;
elem (int value, int minv) : val(value), min(minv) {};
} elem;
stack<elem> s;
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
