剑指offer----队列和栈

1. 用两个栈实现队列的头部出队，尾部入队操作：

class Solution
{
public:
    void push(int node) {
        while(!stack2.empty())
        {
            stack1.push(stack2.top());
            stack2.pop();
        }
        stack1.push(node);
    }
    int pop() {
        while(!stack1.empty())
        {
            stack2.push(stack1.top());
            stack1.pop();
        }
        int ans = stack2.top();
        stack2.pop();
        return ans;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

30、包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为）。

• 解题思路：复杂度是，则不是重装栈，trick是辅助栈进展方式为遇到最小就装它，否则装入当前栈顶元素。

class Solution {
public:
    void push(int value) {
        st1.push(value);
        if(st2.empty())
            st2.push(value);
        else
        {
            int top = st2.top();
            if(top>value)
                st2.push(value);
            else
                st2.push(top);
        }
    }
    void pop() {
        st1.pop();
        st2.pop();
    }
    int top() {
        return st1.top();
    }
    int min() {
        return st2.top();
    }
private:
    stack<int> st1;
    stack<int> st2;
};

31、栈的压入和弹出

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

• 解：比较进栈数组中对每一个进栈的数与出栈数组的第一个元素，相等则对该元素出栈，继续比较进栈数组出栈后的栈顶与出栈数组第二个元素，相等则弹出，否则，继续进栈。若是最后进栈数组为空，则结果匹配正确。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.empty() && popV.empty()) return true;
        if(pushV.empty() || popV.empty() || pushV.size()!=popV.size()) return false;
        
        stack<int> st; 
        for(int i=0,j=0; i<pushV.size();++i)
        {
            st.push(pushV[i]);
            //未越界且相等
            while(j<popV.size() && popV[j]==st.top())
            {
                st.pop();
                j++;
            }
        }
        if(st.empty()) 
            return true;
        else 
            return false;
    }
};

59、队列最大的值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}

1.直接算最大再排除第一个：这个算法总的时间复杂度是O(nk)

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> ans;
        deque<int> index;
        if(num.empty() || size == 1) return num;
        if(size<=0) return vector<int>();  
        int count = 0; //记录滑动窗口大小是否达到
        for(int i=0; i<num.size();++i)
        {
            index.push_back(num[i]);
            count++;
            if(count==size)
            {
                count -= 1;
                ans.push_back(*max_element(index.begin(), index.end()));
                index.pop_front();
            }
        }
        return ans;
    }
};

用双向队列实现，主要是理解思路。
从后删除的情况：只有当 当前数字比队列的后面数字大时。
从前删除的情况： 只有 当 队列前面的数字的序号不在滑动窗口内。

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> res;
        deque<int> s;
        for(unsigned int i=0;i<num.size();++i){
            while(s.size() && num[s.back()]<=num[i])//从后面依次弹出队列中比当前num值小的元素，同时也能保证队列首元素为当前窗口最大值下标,同时排出多个
                s.pop_back();
            //这里的while改为if也是可行的，因为只可能超出一个
            while(s.size() && i-s.front()+1>size)//当当前窗口移出队首元素所在的位置，即队首元素坐标对应的num不在窗口中，需要弹出
                s.pop_front();
            s.push_back(i);//把每次滑动的num下标加入队列
            if(size&&i+1>=size)//当滑动窗口首地址i大于等于size时才开始写入窗口最大值
                res.push_back(num[s.front()]);
        }
        return res;
    }
};