本栏目记录在 剑指offer 刷题中的一些思考和反思，持续更新…

如果觉得我代码太烂，欢迎留言拍砖。🎉

Tip

• 建议PC端查看此文，因为有目录可以参考。
• 此文只列举（浪费时间多的）部分题，如需讨论，欢迎留言或私信。

面试题09. 用两个栈实现队列

传送门：面试题09. 用两个栈实现队列

一、思路

入队时，直接压入 stack01；

出队时，将 stack01 中的元素，全部弹出，并压入 stack02，实现首尾顺序调换，让 stack02 栈顶弹出，再将 stack02 元素依次弹出，压入 stack01。

/*
执行用时 :1144 ms, 在所有 C++ 提交中击败了6.53%的用户
内存消耗 :111.2 MB, 在所有 C++ 提交中击败了100.00%的用户
*/

class CQueue {
public:
    stack<int> stack01;
    stack<int> stack02;

    CQueue() {

    }
    
    void appendTail(int value) {
            stack01.push(value);
    }
    
    int deleteHead() {
        if (stack01.empty()) {
                return -1;
        } else {
            while (!stack01.empty()) {
                stack02.push(stack01.top());
                stack01.pop();
            }
        }
        int hand = stack02.top();
        stack02.pop();
        while (!stack02.empty()) {
            stack01.push(stack02.top());
            stack02.pop();
        }
        return hand;
    }
};

二、优化

思路中的 “再将 stack02 元素依次弹出，压入 stack01” 为多余步骤。

因为只有两个操作，入队和出队。入队从 stack01 完成，直接压栈；出队从 stack02 完成，直接弹出顶部元素，无需考虑中间元素一起存放。

需增加判断，当 stack02 为空，需再次判断 stack01 是否为空

/*
执行用时:632 ms, 在所有 C++ 提交中击败了35.90%的用户
内存消耗:103.6 MB, 在所有 C++ 提交中击败了100.00%的用户
*/
class Queue {
public:
    stack<int> stack01;
    stack<int> stack02;

    CQueue() {

    }
    
    void appendTail(int value) {
            stack01.push(value);
    }
    
    int deleteHead() {
        if (stack02.empty()) {                       //modified
            if (stack01.empty()) {                   //modified
                return -1;
            } else {
                while (!stack01.empty()) {
                    stack02.push(stack01.top());
                    stack01.pop();
                }
            }
        }    
        int hand = stack02.top();
        stack02.pop();
        return hand;
    }
};