剑指offer刷题(持续更新...)

本文最后更新于:6 个月前

本栏目记录在 剑指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;
    }
};

本博客所有文章均个人原创,除特别声明外均采用 CC BY-SA 4.0协议,转载请注明出处!

 目录

致敬李文亮及各路英雄好汉!