8.31cc栈和队列

像是夏日的最后一天

- 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();
 */