2019-12-11 刷题-3（栈）

155-最小栈

• 解法一：此题最简单的做法就是实现两个栈，一个记录当前元素，一个记录当前序列的最小元素。
  代码：

class MinStack {
public:
    stack<int> s;
    stack<int> m;
    /** initialize your data structure here. */
    MinStack() {
    }
    
    void push(int x) {
        s.push(x);
        if (m.empty())
            m.push(x);
        else{
            int cur_min = m.top();
            if (x < cur_min)
                m.push(x);
            else
                m.push(cur_min);
        }
    }
    
    void pop() {
        s.pop();
        m.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return m.top();
    }
};

• 解法二：更厉害一点的做法是，只用一个栈，当前最小值用一个int型记录。如果新压栈的数比当前最小值小，就要把当前最小值先压栈，然后更新当前最小值。
  不过，当新压栈的数与当前最小值相等时，比较容易出错。需要注意：1）当新压栈的数与当前最小值最小时，也要将最小值先压栈，否则出栈时会出错；2）当栈为空时，第一个元素要压栈两次，否则出栈最后一个元素时，会报段错误。
  代码：

class MinStack {
public:
    stack<int> s;
    int cur_min;
    /** initialize your data structure here. */
    MinStack() {
    }
    
    void push(int x) {
        if (s.empty()){
            s.push(x);   //第一个元素要压栈两次
            s.push(x);
            cur_min = x;
        }
        else{
            if (x <= cur_min){   //等号很重要
                s.push(cur_min);
                s.push(x);
                cur_min = x;
            }
            else{
                s.push(x);
            }
        }
    }
    
    void pop() {
        if (s.top() == cur_min){
            s.pop();
            cur_min = s.top();
            s.pop();
        }
        else{
            s.pop();
        }
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return cur_min;
    }
};

225-用队列实现栈

• 解法一：本题最直观的做法还是搞两个队列，一个平时存数据，一个pop的时候临时存放。
  push：O(1)，pop：O(n)。
• 解法二：另一种做法是只使用一个队列，在push的时候就把数据的顺序调整成栈的存放顺序。
  比如push a, b, c：
  1）push a，队列中只有a
  2）push b，此时队列为b a，右边为队头，左边为队尾。将a出队后再push，队列变为a b。
  3）push c，此时队列为c a b，将a和b分别出队再入队，队列变为a b c.
  push：O(n), pop: O(1)。
  代码：

class MyStack {
public:
    /** Initialize your data structure here. */
    queue <int> q1;
    int top_ele;
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        if (q1.empty())
            q1.push(x);
        else {
            int q_len = q1.size();
            q1.push(x);
            while (q_len--) {
                int tmp = q1.front();
                q1.pop();
                q1.push(tmp);
            }
        }
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int rm_ele = q1.front();
        q1.pop();
        return rm_ele;
    }

    /** Get the top element. */
    int top() {
        return q1.front();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return q1.empty();
    }
};

232-用栈实现队列
双栈法，一个主栈，一个辅助栈。push的时候只push到主栈中。

• 解法一：维护一个top值，pop的时候将主栈的元素都倒到辅助栈中，完成pop再倒回主栈中。
  时间复杂度：push O(1), pop O(n), top O(1)
  这种做法比较简单，就不放代码了。

• 解法二：分别维护一个top_all和top_s1用来存放模拟队列的队头和主栈的栈底。pop的时候将主栈的元素都倒到辅助栈中，完成pop后也不倒回，之后每次pop都从辅助栈中取，直到辅助栈为空，再将主栈元素倒入辅助栈中。平均下来，每个元素pop的代价也是O(1)。
  时间复杂度：push O(1), pop O(1), top O(1)。
  代码：

class MyQueue {
public:
    /** Initialize your data structure here. */
    stack <int> s1;  // store elements with stack order
    stack <int> s2;  // store elements with queue order
    int top_all, top_s1;
    MyQueue() {
    }

    /** Push element x to the back of queue. */
    void push(int x) {
        if (s1.empty() && s2.empty()) {
            top_all = x;
        }
        if (s1.empty() && !s2.empty()) {
            top_s1 = x;   // s1栈底元素，用于s2空时更新队头元素
        }
        s1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int rm_ele;
        if (!s2.empty()) {
            // pop element from s2
            rm_ele = s2.top();
            s2.pop();
            // update top_all
            if (s2.empty())
                top_all = top_s1;
            else
                top_all = s2.top();
            return rm_ele;
        }
        // transmit all elements from s1 to s2
        while (!s1.empty()) {
            int tmp = s1.top();
            s2.push(tmp);
            s1.pop();
        }
        rm_ele = s2.top();
        s2.pop();
        if (!s2.empty())
            // update top_all
            top_all = s2.top();
        return rm_ele;
    }

    /** Get the front element. */
    int peek() {
        return top_all;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty() && s2.empty();
    }
};

不过，这两种解法提交后运行时间都是0ms，反而是如果不维护top元素，每次取队头元素都要倒一遍数据的做法用时比较多，可能测试样例中比较多peek操作。而维护top元素的代价很小，所以还是很值得的。