手撕栈队列

【面试题07：用两个栈实现队列】

题目：利用两个栈实现队列的插入，取队首，判断非空等函数。
拓展：用两个队列实现栈，或用一个队列实现栈。

class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        stack1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() { 
        int result = peek();
        stack2.pop();
        return result; 
    }
    
    /** Get the front element. */
    int peek() {
        if(stack2.size() == 0){
            while(stack1.size()>0){
                stack2.push(stack1.top());
                stack1.pop();
            }
        } 
        return stack2.top(); 
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {  
        return stack1.empty() && stack2.empty(); 
        
    }
private:
    stack<int>stack1;
    stack<int>stack2;
};

class MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() { 
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        queue1.push(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int result = top();
        queue1.pop(); 
        queue1 = queue2;
        queue2.clear();
        return  result;
    }
    
    /** Get the top element. */
    int top() {
        while(queue1.size()>1){
            queue2.push(queue1.front());
            queue1.pop();
        }
        return queue1.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return queue1.empty() && queue2.empty();
    }

private:
    queue<int>queue1;
    queue<int>queue2;
};

class Stack {
    queue<int> q;
public:
    void push(int x) {
        q.push(x);
        for (int i=1; i<q.size(); i++) {
            q.push(q.front());
            q.pop();
        }
    }

    void pop() {
        q.pop();
    }

    int top() {
        return q.front();
    }

    bool empty() {
        return q.empty();
    }
};

【面试题21：包含min函数的栈】 Min Stack

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小素的min 函数。在该栈中，调用min、push 及pop的时间复杂度都是0(1)。
思路：利用一个辅助栈存放实时的最小值，与原栈空间保持一致。

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        Stack.push(x);
        if(minStack.empty() ||x < minStack.top())
            minStack.push(x);
        else
            minStack.push(minStack.top()); 
    }
    
    void pop() {
        if(!Stack.empty()){
            Stack.pop();
            minStack.pop();
        } 
    }
    
    int top() {
        return Stack.top();
    }
    
    int getMin() {
        return minStack.top();
    }
private:
    stack<int>Stack;
    stack<int>minStack;
};

【面试题22：栈的压入、弹出序列】

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
思路：采用一个辅助栈，当栈顶元素不等于弹出序列元素时，将压入序列元素压入辅助栈至相等。然后弹出辅助栈顶，讨论下一个弹出序列元素。如压入序列元素元素压完后辅助栈顶仍不等弹出序列元素，即false。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.empty() || popV.empty()) return false;
        stack<int>auxStack;
        int pPushV=0;
        int pPopV=0;
        while( pPopV<popV.size()){
            while(pPushV <= pushV.size() && 
                  (auxStack.empty()|| auxStack.top() != popV[pPopV]))
                auxStack.push(pushV[pPushV++]); 
            if(auxStack.top() != popV[pPopV]) return false;
            auxStack.pop();
            pPopV++; 
        }
        return true;
    }

【面试题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]}。
思路：采用一个双向队列储存窗口下的最大值以及可能最大值，遇到较大的数，则循环pop_back；遇到超过窗口尺寸的，则pop_front。

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int>maxInWin;
        if(num.size()>=size && size>=1){
            deque<int>index;
            for(unsigned int i=0; i<size; i++){
                while(!index.empty() && num[i]>=num[index.back()])
                    index.pop_back();
                index.push_back(i);
            }
            for(unsigned int i=size; i<num.size(); i++){
                maxInWin.push_back(num[index.front()]);
                while(!index.empty() && num[i]>=num[index.back()])
                    index.pop_back();
                if(!index.empty() && index.front() <= int(i-size))
                {//判断队头的下标是否超出size大小，如果超过，要删除队头元素
                    index.pop_front();
                } 
                index.push_back(i);//将当前下标压入队尾，因为可能在未来是最大值
            }
            maxInWin.push_back(num[index.front()]);
        }
        return maxInWin;
    }
};