精明的程序員——堆棧和隊(duì)列的相互轉(zhuǎn)換
寫這篇的靈感，是源自看到網(wǎng)上一個(gè)Google的面經(jīng)。以下一段話引自面經(jīng)原文：
“第三道題目他先是說(shuō)這東西可能沒(méi)用，說(shuō)stack和queue哪個(gè)更基本一些，我馬上說(shuō)stack，并告訴他我知道是stack，但不知道為什么是stack，他又具體舉了個(gè)例子，說(shuō)1和-1哪個(gè)更基本，我?guī)缀鯖](méi)思考就說(shuō)是1，他說(shuō)是-1，因?yàn)?1*-1可以得到1，而1怎么也得不到-1，我辯解說(shuō)這要看你怎么定義“基本”這個(gè)詞，于是他回到了stack和queue，說(shuō)其中一個(gè)可以模擬另一個(gè)，而反之不行，我重復(fù)了他的問(wèn)題，說(shuō)等同于系統(tǒng)只提供了stack這個(gè)數(shù)據(jù)結(jié)構(gòu)，沒(méi)有提供queue，要我用stack模擬queue，但是最后我繞了一大圈，把問(wèn)題搞得很復(fù)雜，甚至往hanoi方向上想，也沒(méi)想出如何解決這個(gè)問(wèn)題，當(dāng)然掛了電話以后很快就知道怎么弄了，一只手拿著電話聽(tīng)筒確實(shí)沒(méi)法思考...”
看完這份面經(jīng)，我的第一反應(yīng)是驚訝。記得在大四的時(shí)候Intel給我電面時(shí)，Danming就問(wèn)我“如何用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列”，我當(dāng)時(shí)的回答讓他很滿意。那個(gè)時(shí)候都能輕松答出的題目，現(xiàn)在想當(dāng)然覺(jué)得不困難?？吹紾oogle也會(huì)問(wèn)這么簡(jiǎn)單的題目，不免有點(diǎn)驚訝。
靜下心來(lái)，透過(guò)現(xiàn)象看本質(zhì)。同樣一個(gè)問(wèn)題，感覺(jué)這個(gè)Google的面試官問(wèn)出來(lái)就很有哲理。但是當(dāng)我細(xì)心想想之后的時(shí)候，才發(fā)現(xiàn)這其中漏洞百出。
-1和1哪個(gè)更基本
哪個(gè)更基本？我想每個(gè)人的第一反應(yīng)都會(huì)像求職者所答一樣：是1。答后卻得到面試官的否定一定讓人不免有些驚訝。面試官補(bǔ)上一句貌似頗有道理的解釋，又讓人貌似恍然大悟。但如求職者所辯解，怎么定義“基本”這個(gè)詞？這個(gè)面試官根本沒(méi)有給出嚴(yán)謹(jǐn)?shù)亩x。因?yàn)閮蓚€(gè)-1相乘可以得到1，所以-1更基本？那么我們可以說(shuō)用三個(gè)1，讓其中一個(gè)減去另外兩個(gè)就可以得到-1。又如何解釋？或是更簡(jiǎn)單的，對(duì)一個(gè)-1做平方運(yùn)算，會(huì)得到1；反之，對(duì)1做開(kāi)方運(yùn)算，也可以得到-1。這里有一個(gè)讓人混淆的一點(diǎn)就是，我們除了運(yùn)算子是-1或1之外，沒(méi)有在意運(yùn)算的本質(zhì)又引入了其他的數(shù)字。例如-1*-1=1，實(shí)際是有兩個(gè)運(yùn)算子，面試官此時(shí)已經(jīng)悄悄引入了一個(gè)數(shù)字2。哪怕是一元運(yùn)算符平方即2次方，也蘊(yùn)含著一個(gè)2在其中。學(xué)計(jì)算機(jī)的人都知道，有了2，就有了世界。
那么究竟哪個(gè)真的更基本一些？我相信答案是1。我也相信面試官小學(xué)數(shù)學(xué)先學(xué)到的應(yīng)該是1，而后學(xué)的-1。因?yàn)槿绻麤](méi)有1，-1不會(huì)有任何意義，就根本不會(huì)存在-1。
堆棧可以模擬隊(duì)列
這是面試官信心滿滿提出的問(wèn)題，求職者在放下電話之后也恍然大悟，其實(shí)答案很簡(jiǎn)單。如果你之前沒(méi)有想過(guò)這個(gè)問(wèn)題，請(qǐng)先不要繼續(xù)讀下去，可以先獨(dú)立思考一個(gè)這個(gè)答案，再看后文。其實(shí)答案很簡(jiǎn)單，就是把數(shù)據(jù)push到棧A，再把棧A的數(shù)據(jù)依次pop并push到棧B。那么先入棧A的數(shù)據(jù)就會(huì)移到棧B的頂部，對(duì)棧B進(jìn)行pop時(shí)就會(huì)先出棧B。恰恰符合了隊(duì)列的本質(zhì)——First in First out。
反之不行？
往往前輩（一個(gè)統(tǒng)稱，包括老師，面試官，老板，領(lǐng)導(dǎo)等）說(shuō)不行的，給人們的感覺(jué)就是“真的不行”。而忽略了兩個(gè)問(wèn)題“是否真的不行？”和“為什么不行？”學(xué)習(xí)任何知識(shí)，思考這兩個(gè)問(wèn)題都是有益的，絕對(duì)不會(huì)多余，哪怕真的是“不行”。所以我就去想，結(jié)果發(fā)現(xiàn)兩個(gè)隊(duì)列也是可以模擬堆棧的。方法也很簡(jiǎn)單：把數(shù)據(jù)都enqueue到隊(duì)列A，如果你想取出最后一個(gè)enqueue的數(shù)據(jù)（即Last
in），那么就把隊(duì)列A的數(shù)據(jù)依次dequeue并enqueue到隊(duì)列B，但是不能全部移到隊(duì)列B，要留下一個(gè)。這一個(gè)就是你需要的數(shù)據(jù)把它dequeue出來(lái)，就會(huì)得到Last in的數(shù)據(jù)。這個(gè)過(guò)程，相當(dāng)于對(duì)棧進(jìn)行了依次pop操作，符合——Last in First out。需要再次pop的時(shí)候，按照同樣的方法，只需將對(duì)A、B的操作交換就可以了。
如此簡(jiǎn)單的問(wèn)題，不知道為什么面試官卻說(shuō)了一句“反之不行”。即便真的是反之不行，就真的能說(shuō)明棧比隊(duì)列更“基本”嗎？
一個(gè)堆棧和一個(gè)隊(duì)列也可以相互轉(zhuǎn)換？
剛剛看到網(wǎng)上有些人總結(jié)的面試題中出現(xiàn)了“用一個(gè)堆棧實(shí)現(xiàn)一個(gè)隊(duì)列”和“用一個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)堆?！保幻庾屛矣行┏泽@。第一反應(yīng)是不可行，為什么不可行呢？比如，你想要一個(gè)棧底部的數(shù)據(jù)，必然需要將頂部的數(shù)據(jù)pop出來(lái)啊，那么pop出來(lái)之后放在哪里呢，前提是只有一個(gè)棧，沒(méi)有別的數(shù)據(jù)結(jié)構(gòu)了?。勘е@種質(zhì)疑的態(tài)度，繼續(xù)看答案：“用一個(gè)堆棧實(shí)現(xiàn)一個(gè)隊(duì)列。思路：用遞歸的方法把數(shù)據(jù)從最底部移出來(lái)。用一個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)堆棧。思路：對(duì)于每次pop，用遞歸的方法反轉(zhuǎn)隊(duì)列元素的排列，然后返回第一個(gè)元素”。答案思路后面還跟著一份實(shí)現(xiàn)的代碼。我看了思路已經(jīng)心知肚明，沒(méi)有再看代碼。因?yàn)槲铱吹健斑f歸“二字，答題者在這里用”遞歸“的說(shuō)法悄悄的引入了一個(gè)棧，這與利用-1*-1=1來(lái)引入2是同樣的伎倆。也就是說(shuō)，所謂的“用一個(gè)堆棧實(shí)現(xiàn)一個(gè)隊(duì)列”，實(shí)質(zhì)還是用了兩個(gè)棧。
后記
這個(gè)面試的題目其實(shí)沒(méi)有多大的意思，不論是用棧來(lái)實(shí)現(xiàn)隊(duì)列還是用隊(duì)列實(shí)現(xiàn)棧，本質(zhì)是要把當(dāng)前擁有的數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)都挪到一邊去，取出來(lái)剩下的最后那一個(gè)，就是需要的結(jié)果。至于前面那些數(shù)據(jù)都挪到哪里了，可以說(shuō)只要能裝得下，挪到了哪里都無(wú)所謂?？梢赃@樣說(shuō)，一個(gè)棧加”另一個(gè)數(shù)據(jù)結(jié)構(gòu)“就可以實(shí)現(xiàn)一個(gè)隊(duì)列（反之亦然），這”另一個(gè)數(shù)據(jù)結(jié)構(gòu)“可以是一個(gè)棧，也可以是一個(gè)隊(duì)列，哪怕是一個(gè)b樹(shù)，一個(gè)圖，都無(wú)所謂。
以上的所有，都是我弱弱的思考，目的僅是品味愉快的思考過(guò)程，觀點(diǎn)中必然有不嚴(yán)謹(jǐn)不科學(xué)的各種問(wèn)題，非常歡迎大家拍磚。
|
