剑指offer-队列＆栈

1.用两个栈实现队列

实现一个函数：将一个栈倒腾到另外一个栈。

class Solution {
    void inToOut() {
        if (out.empty()) {
            while (in.size()) {
                int num = in.top();
                in.pop();
                out.push(num);
            }
        }
    }
public:
    void push(int node) {
        in.push(node);
        inToOut();
    }

    int pop() {
        inToOut();
        int num = out.top();
        out.pop();
        return num;
    }
private:
    stack<int> in;
    stack<int> out;
};

2.包含min函数的栈

实现一个辅助栈，该栈只存储当前栈中最小的数值。

class Solution {
    stack<int> stk, minStk;
public:
    void push(int value) {
        stk.push(value);
        if (minStk.empty()) {
            minStk.push(value);
        } else {
            int num = ::min(minStk.top(), value);
            minStk.push(num);
        }
    }
    void pop() {
        stk.pop();
        minStk.pop();
    }
    int top() {
        return stk.top();
    }
    int min() {
        return minStk.top();
    }
};

3.栈的压入弹出序列

    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if (pushV.empty() and popV.empty()) return true;
        if (pushV.size() != popV.size()) return false;
        stack<int> stk;
        int popId = 0;
        for (int i = 0; i < pushV.size(); ++i){
            stk.push(pushV[i]);
            while (stk.size() && stk.top() == popV[popId]) {
                stk.pop();
                ++popId;
            }
        }
        return stk.empty();
    }

4.翻转单词序列

使用字符串流

    string ReverseSentence(string str) {
        if (str.empty()) return str;
        istringstream iss(str);
        string temp;
        vector<string> vec;
        while (iss >> temp) {
            vec.emplace_back(temp);
        }
        string res;
        for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
            res += *it + ' ';
        }
        res.pop_back();
        return res;
    }

5.滑动窗口的最大值

维护一个单调递增双端队列：大小不会超过规定窗口大小，确保单调递增。

    vector<int> maxInWindows(const vector<int>& nums, unsigned int size) {
        vector<int> res;
        if (size == 0 or nums.empty()) return res;
        deque<int> q;
        for (int i = 0; i < nums.size(); ++i) {
            if (q.size() and i - q.front() >= size) q.pop_front();
            while (q.size() and nums[q.back()] <= nums[i]) q.pop_back();
            q.push_back(i);
            if (i + 1 >= size) res.emplace_back(nums[q.front()]);
        }
        return res;
    }