两个栈实现一个队列-阿里云开发者社区

开发者社区> this_is_bill> 正文

两个栈实现一个队列

简介:
+关注继续查看

一、题目

用C++描述,题目大致是这样的:

已知下面Stack类及其3个方法Push、Pop和 Count,请用2个Stack实现Queue类的入队(Enqueue)出队(Dequeue)方法。

class Stack
{
…
public:
         void Push(int x); // Push an element in stack;
         int Pop();  // Pop an element out of stack;
         int Count() const;     // Return the number of the elements in stack;
…
};

class Queue
{
…
public:
         void Enqueue(int x);
         int Dequeue();

private:
         Stack s1;
         Stack s2;
…
};

这道题应该不算难,比起《编程之美》中微软那些什么“翻烙饼”的面试题,难度上差远了。况且,由于时间关系,我一般也不要求面试者写代码,只描述清楚思路即可。出这道题,主要考察3点:

  1. 在短时间内,能不能找到解决这道题的足够清晰的思路(思维是否敏捷、清晰)。
  2. 能不能在单向表述中,清楚地描述自己的思路和想法(表述能力是否达到要求)。
  3. 对于某些具体细节,能不能考虑到(是否足够细致)。

总体上,以10人为例,实际的结果大致是:

  1. 8个人可以找到解决答案,2个人无法找到答案。
  2. 8个找到答案的人中,6个找到的方法相同,2个人找到其它变种。
  3. 在这8个人中,有1个人可以不经提示,同时想到大众方法和变种。

二、解法

法一:

大多数人的思路是:始终维护s1作为存储空间,以s2作为临时缓冲区。
入队时,将元素压入s1。
出队时,将s1的元素逐个“倒入”(弹出并压入)s2,将s2的顶元素弹出作为出队元素,之后再将s2剩下的元素逐个“倒回”s1。
见下面示意图:

这里写图片描述

上述思路,可行性毋庸置疑。但有一个细节是可以优化一下的。即:在出队时,将s1的元素逐个“倒入”s2时,原在s1栈底的元素,不用“倒入”s2(即只“倒”s1.Count()-1个),可直接弹出作为出队元素返回。这样可以减少一次压栈的操作。约有一半人,经提示后能意识到此问题。

上述思路,有些变种,如:
入队时,先判断s1是否为空,如不为空,说明所有元素都在s1,此时将入队元素直接压入s1;如为空,要将s2的元素逐个“倒回”s1,再压入入队元素。
出队时,先判断s2是否为空,如不为空,直接弹出s2的顶元素并出队;如为空,将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。
有些人能同时想到大众方法和变种,应该说头脑还是比较灵光的。

相对于第一种方法,变种的s2好像比较“懒”,每次出队后,并不将元素“倒回”s1,如果赶上下次还是出队操作,效率会高一些,但下次如果是入队操作,效率不如第一种方法。我有时会让面试者分析比较不同方法的性能。我感觉(没做深入研究),入队、出队操作随机分布时,上述两种方法总体上时间复杂度和空间复杂度应该相差无几(无非多个少个判断)。

法二:

真正性能较高的,其实是另一个变种。即:
入队时,将元素压入s1。
出队时,判断s2是否为空,如不为空,则直接弹出顶元素;如为空,则将s1的元素逐个“倒入”s2,把最后一个元素弹出并出队。
这个思路,避免了反复“倒”栈,仅在需要时才“倒”一次。但在实际面试中很少有人说出,可能是时间较少的缘故吧。

以上几个思路乍看没什么问题了,但其实还是有个细节要考虑的。其实无论什么方法和情况,都要考虑没有元素可供出队时的处理(2个栈都为空的时候,出队操作一定会引起异常)。在实际写代码时,忽略这些判断或异常处理,程序会出现问题。所以,能不能考虑到这些细节,也体现了个人的素养。


参考资料

[1] http://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
程序员知识体系探索:点、线、面、体(下)
程序员知识体系探索:点、线、面、体(下)
4 0
基于 H5 Canvas "指纹识别" 技术 【浏览器指纹 VS Canvas指纹】
基于 H5 Canvas "指纹识别" 技术 【浏览器指纹 VS Canvas指纹】
23 0
VS Code识别编辑规范,ESlint规则,VS Code保存去掉自动加分号、逗号、双引号
书写规范是非常重要的,除了统一,还要简洁。 1、VS Code识别编辑规范 在项目根目录新建.editorconfig文件,加入设置:
19 0
flutter 版本控制fvm
1先安装 choco powershell 管理员身份运行 不会的话,先打开一个powershell 窗口 ,然后右击任务栏,选择第一个,即可进入
4 0
【Typescript入门手册】类型进阶
【Typescript入门手册】类型进阶
12 0
领域建模:分清问题域和问题解决域(下)
领域建模:分清问题域和问题解决域(下)
4 0
终身学习与传统文化[增强版]
最近H同学问了我2个问题。一是我越参加社群活动,就越没有自信了(大家都挺牛的,连友强都是,不仅能写,排版能力也提升了);二是张同学是我老板,他擅长做会议引导,他竟然让我策划组织一次会议,我也怕丢脸。 那么问题来了,有哪些解法呢?
5 0
Spring Boot 基础教程:使用 Swagger3 生成 API 接口文档
主要介绍如何使用 Spring Boot 集成 Swagger3,构建我们自己的 API 接口文档,并对比了 Swagger2 和 Swagger3 的区别,让我们从 Swagger2 向 Swagger3 过渡更加顺滑。
6 0
漫谈“架构团队”之组织架构(下)
漫谈“架构团队”之组织架构(下)
5 0
user-modify VS contenteditable 【实现掘金沸点话题标签】
user-modify VS contenteditable 【实现掘金沸点话题标签】
16 0
+关注
331
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载