剑指offer-JZ5

c++
本题考查最简单的队列和栈的性质。
队列：先进先出 [1,2,3,4]------4,3,2,1
栈 ：后进先出 [1,2,3,4]------1,2,3,4
想要用栈实现队列，最简单的是
a---[1,2,3,4] 出栈然后入栈b [4,3,2,1]
代码如下：

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
    void copy(stack<int> &a, stack<int> &b){
        while(a.size()){
            b.push(a.top());
            a.pop();
        }
    }
    int pop() {
        copy(stack1,stack2);
        int top_num = stack2.top();
        stack2.pop();
        copy(stack2,stack1);
        return top_num;
    }

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

但是频繁复制其实有优化空间的。
比如，两个栈实际上不需要每次出队列就赋值，可以等b结束了再赋值，即
a [1,2,3,4] b[] ---------出队列 ------a[],b[4,3,2,1]
---进队列
a[5,6,7]----b[4,3,2,1]
直到b出完
再进行转换

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
    int pop() {


        if(! stack2.empty()){
            int top_num = stack2.top();
            stack2.pop();
            return top_num;
        }else if (!stack1.empty()){
            while(stack1.size()){
                stack2.push(stack1.top());
                stack1.pop();
            }
            int top_num = stack2.top();
            stack2.pop();
            return top_num;
        }else{
            return stack2.top();
        }

    }

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