写这篇的灵感,是源自看到网上一个Google的面经。以下一段话引自面经原文:
“第三道题目他先是说这东西可能没用,说stack和queue哪个更基本一些,我马上说stack,并告诉他我知道是stack,但不知道为什么是stack,他又具体举了个例子,说1和-1哪个更基本,我几乎没思考就说是1,他说是-1,因为-1*-1可以得到1,而1怎么也得不到-1,我辩解说这要看你怎么定义“基本”这个词,于是他回到了stack和queue,说其中一个可以模拟另一个,而反之不行,我重复了他的问题,说等同于系统只提供了stack这个数据结构,没有提供queue,要我用stack模拟queue,但是最后我绕了一大圈,把问题搞得很复杂,甚至往hanoi方向上想,也没想出如何解决这个问题,当然挂了电话以后很快就知道怎么弄了,一只手拿着电话听筒确实没法思考...”
看完这份面经,我的第一反应是惊讶。记得在大四的时候Intel给我电面时,Danming就问我“如何用两个栈实现一个队列”,我当时的回答让他很满意。那个时候都能轻松答出的题目,现在想当然觉得不困难。看到Google也会问这么简单的题目,不免有点惊讶。
静下心来,透过现象看本质。同样一个问题,感觉这个Google的面试官问出来就很有哲理。但是当我细心想想之后的时候,才发现这其中漏洞百出。
-1和1哪个更基本
哪个更基本?我想每个人的第一反应都会像求职者所答一样:是1。答后却得到面试官的否定一定让人不免有些惊讶。面试官补上一句貌似颇有道理的解释,又让人貌似恍然大悟。但如求职者所辩解,怎么定义“基本”这个词?这个面试官根本没有给出严谨的定义。因为两个-1相乘可以得到1,所以-1更基本?那么我们可以说用三个1,让其中一个减去另外两个就可以得到-1。又如何解释?或是更简单的,对一个-1做平方运算,会得到1;反之,对1做开方运算,也可以得到-1。这里有一个让人混淆的一点就是,我们除了运算子是-1或1之外,没有在意运算的本质又引入了其他的数字。例如-1*-1=1,实际是有两个运算子,面试官此时已经悄悄引入了一个数字2。哪怕是一元运算符平方即2次方,也蕴含着一个2在其中。学计算机的人都知道,有了2,就有了世界。
那么究竟哪个真的更基本一些?我相信答案是1。我也相信面试官小学数学先学到的应该是1,而后学的-1。因为如果没有1,-1不会有任何意义,就根本不会存在-1。
堆栈可以模拟队列
这是面试官信心满满提出的问题,求职者在放下电话之后也恍然大悟,其实答案很简单。如果你之前没有想过这个问题,请先不要继续读下去,可以先独立思考一个这个答案,再看后文。其实答案很简单,就是把数据push到栈A,再把栈A的数据依次pop并push到栈B。那么先入栈A的数据就会移到栈B的顶部,对栈B进行pop时就会先出栈B。恰恰符合了队列的本质——First in First out。
反之不行?
往往前辈(一个统称,包括老师,面试官,老板,领导等)说不行的,给人们的感觉就是“真的不行”。而忽略了两个问题“是否真的不行?”和“为什么不行?”学习任何知识,思考这两个问题都是有益的,绝对不会多余,哪怕真的是“不行”。所以我就去想,结果发现两个队列也是可以模拟堆栈的。方法也很简单:把数据都enqueue到队列A,如果你想取出最后一个enqueue的数据(即Last in),那么就把队列A的数据依次dequeue并enqueue到队列B,但是不能全部移到队列B,要留下一个。这一个就是你需要的数据把它dequeue出来,就会得到Last in的数据。这个过程,相当于对栈进行了依次pop操作,符合——Last in First out。需要再次pop的时候,按照同样的方法,只需将对A、B的操作交换就可以了。
如此简单的问题,不知道为什么面试官却说了一句“反之不行”。即便真的是反之不行,就真的能说明栈比队列更“基本”吗?
一个堆栈和一个队列也可以相互转换?
刚刚看到网上有些人总结的面试题中出现了“用一个堆栈实现一个队列”和“用一个队列实现一个堆栈”,不免让我有些吃惊。第一反应是不可行,为什么不可行呢?比如,你想要一个栈底部的数据,必然需要将顶部的数据pop出来啊,那么pop出来之后放在哪里呢,前提是只有一个栈,没有别的数据结构了啊?抱着这种质疑的态度,继续看答案:“用一个堆栈实现一个队列。思路:用递归的方法把数据从最底部移出来。用一个队列实现一个堆栈。思路:对于每次pop,用递归的方法反转队列元素的排列,然后返回第一个元素”。答案思路后面还跟着一份实现的代码。我看了思路已经心知肚明,没有再看代码。因为我看到“递归“二字,答题者在这里用”递归“的说法悄悄的引入了一个栈,这与利用-1*-1=1来引入2是同样的伎俩。也就是说,所谓的“用一个堆栈实现一个队列”,实质还是用了两个栈。
后记
这个面试的题目其实没有多大的意思,不论是用栈来实现队列还是用队列实现栈,本质是要把当前拥有的数据结构中的数据都挪到一边去,取出来剩下的最后那一个,就是需要的结果。至于前面那些数据都挪到哪里了,可以说只要能装得下,挪到了哪里都无所谓。可以这样说,一个栈加”另一个数据结构“就可以实现一个队列(反之亦然),这”另一个数据结构“可以是一个栈,也可以是一个队列,哪怕是一个b树,一个图,都无所谓。
以上的所有,都是我弱弱的思考,目的仅是品味愉快的思考过程,观点中必然有不严谨不科学的各种问题,非常欢迎大家拍砖。
ref:http://blog.csdn.net/baby313/article/details/8059884
分享到:
相关推荐
该文件包括堆栈的头文件(Seq开头)和链表的头文件(Lin开头),另外还实现了十进制转化为八进制、对称串判断和带头结点的单循环链表实现链式队列
线性表、堆栈、队列实现源码,C++实现,如果有问题请大家给我留言http://blog.csdn.net/tiandixuanwuliang
数组、链表、堆栈和队列、线性表和顺序表 数组和链表.pdf
堆栈和队列基本操作的编程实现(2学时,验证型),掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现,存储结构可以在顺序结构或链接结构中任选,也可以全部实现。也鼓励学生利用基本操作进行一些...
是学习堆栈和队列的非常好资料,堆栈和队列是C语言编程中经常需要用到的,不错的资源
关于C++数据结构堆栈和队列的PPT,希望需要的朋友能用的上
只用堆栈实现队列只用堆栈实现队列只用堆栈实现队列
数据结构实验:堆栈与队列; 包括3个代码和实验报告: 括号匹配完成、 利用栈队列逆置 、栈的操作
算法面试通关40讲完整课件 08-10 堆栈、队列 算法面试通关40讲完整课件 08-10 堆栈、队列 算法面试通关40讲完整课件 08-10 堆栈、队列 算法面试通关40讲完整课件 08-10 堆栈、队列 算法面试通关40讲完整课件 08-10 ...
实验五 堆栈和队列的应用 一、实验目的 掌握堆栈和队列的使用。 二、实验内容 1、计算数学表达式的值。 输入数学表达式,输出表达式的计算结果。数学表达式由单个数字和运算符“+”、“-”、“*”、“/”、“(、...
在计算机领域中,堆栈和队列是不可忽视的概念。堆栈是一种数据项按顺序排列的数据结构,只能在一端(称为栈顶——top)进行数据的插入与删除。队列也是一种数据项按顺序排列的数据结构,但它的特殊之处在于,一端...
常用数据结构(堆栈,队列,列表)JAVA代码
数据结构实验 堆栈或队列基本操作的编程实现
建立堆栈和队列的数据结构并模拟堆栈和队列的操作。内有实验报告
数据结构中用C++编写的关于栈的源代码,对栈和队列的应用,建立栈,出栈等等
只是清华大学出版社的基本教程,堆栈和队列的基本内容
第3章 堆栈和队列 第3章
通过C语言的程序演示堆栈和队列先进后出和先进先出的特性,是初学者更容易理解二者的关系和本质。
新编数据结构第三章,pdf格式,详细讲解了堆栈和队列的相关概念,含程序代码
数据结构,用队列跟堆栈来判断回文,利用堆栈的先进后出和队列的先进先出的特性