夯实C++基础之刷题：9 用栈实现队列

两个栈 实现先进先出，从左边的栈进去，弹出之前在第二个栈”绕一遍“再弹出
需要注意的是，C++中stack.top()函数并不pop()，需要手动pop

class MyQueue {
    stack st;
    stack tmp;
public:
    MyQueue() {
    }
    
    void push(int x) {
        // if(!tmp.empty())//右边有数的话，就直接压入左边
        st.push(x);
    }
    
    int pop() {
        if(tmp.empty())//右边空了，又要弹出就把左边的数先转到右边，再pop
        {
           while(!st.empty())
            {
                tmp.push(st.top());
                st.pop();
            } 
        }
        int val=tmp.top();
        tmp.pop();
        return val;    
    }
    
    int peek() {
        if(tmp.empty())
        {
           while(!st.empty())
            {
                tmp.push(st.top());
                st.pop();
            } 
        }
        return tmp.top();
    }
    
    bool empty() {
        return st.empty() && tmp.empty();
    }
};

类似于尾插法，一个栈只起到“绕一圈”的目的，有新元素进来了，就把已经可以先进先出的元素拎出来，把新元素放到最后放好了，再把之前有序的放回去。这样只需要在push的时候操作，其他top peek都可以正常操作

class MyQueue {
    stack st;
public:
    MyQueue() {

    }
    
    void push(int x) {
        stack tmp;
        while(!st.empty())//把所有元素都先转移出来
        {
            tmp.push(st.top());
            st.pop();
        }
        st.push(x);//让新元素到最下面
        //新元素入座完成，把原来的挪回来，这样原来的就在新元素之前了，在st中就实现了队列的要求
        while(!tmp.empty())
        {
            st.push(tmp.top());
            tmp.pop();
        }
    }
    
    int pop() {
        int val = st.top();
        st.pop();
        return val;
    }
    
    int peek() {
        return st.top();
    }
    
    bool empty() {
        return st.empty();
    }
};