探討:用兩個棧實現一個隊列(我作為面試官的小結)

2020-01-26 16:03:27

字體：大中小

來源：轉載

供稿：網友

兩年前從網上看到一道面試題：用兩個棧（Stack）實現一個隊列（Queue）。覺得不錯，就經常拿來面試，幾年下來，做此題的應該有幾十人了。通過對面試者的表現和反應，有一些統計和感受，在此做個小結。

用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個人無法找到答案（即使進行了必要的提示，曾經有位號稱美國MIT深造2年，之后在Google美國公司工作過8個月的兄弟，也沒做出來）。
2.8個找到答案的人中，6個找到的方法相同，2個人找到其它變種。
3.在這8個人中，有1個人可以不經提示，同時想到大眾方法和變種。

大多數人的思路是：始終維護s1作為存儲空間，以s2作為臨時緩沖區。
入隊時，將元素壓入s1。
出隊時，將s1的元素逐個“倒入”（彈出并壓入）s2，將s2的頂元素彈出作為出隊元素，之后再將s2剩下的元素逐個“倒回”s1。
見下面示意圖：

2Stacks1Queue

上述思路，可行性毋庸置疑。但有一個細節是可以優化一下的。即：在出隊時，將s1的元素逐個“倒入”s2時，原在s1棧底的元素，不用“倒入”s2（即只“倒”s1.Count()-1個），可直接彈出作為出隊元素返回。這樣可以減少一次壓棧的操作。約有一半人，經提示后能意識到此問題。

上述思路，有些變種，如：
入隊時，先判斷s1是否為空，如不為空，說明所有元素都在s1，此時將入隊元素直接壓入s1；如為空，要將s2的元素逐個“倒回”s1，再壓入入隊元素。
出隊時，先判斷s2是否為空，如不為空，直接彈出s2的頂元素并出隊；如為空，將s1的元素逐個“倒入”s2，把最后一個元素彈出并出隊。
有些人能同時想到大眾方法和變種，應該說頭腦還是比較靈光的。

相對于第一種方法，變種的s2好像比較“懶”，每次出隊后，并不將元素“倒回”s1，如果趕上下次還是出隊操作，效率會高一些，但下次如果是入隊操作，效率不如第一種方法。我有時會讓面試者分析比較不同方法的性能。我感覺（沒做深入研究），入隊、出隊操作隨機分布時，上述兩種方法總體上時間復雜度和空間復雜度應該相差無幾（無非多個少個判斷）。

真正性能較高的，其實是另一個變種。即：
入隊時，將元素壓入s1。
出隊時，判斷s2是否為空，如不為空，則直接彈出頂元素；如為空，則將s1的元素逐個“倒入”s2，把最后一個元素彈出并出隊。
這個思路，避免了反復“倒”棧，僅在需要時才“倒”一次。但在實際面試中很少有人說出，可能是時間較少的緣故吧。

以上幾個思路乍看沒什么問題了，但其實還是有個細節要考慮的。其實無論什么方法和情況，都要考慮沒有元素可供出隊時的處理（2個棧都為空的時候，出隊操作一定會引起異常）。在實際寫代碼時，忽略這些判斷或異常處理，程序會出現問題。所以，能不能考慮到這些細節，也體現了個人的素養。

個人感覺，這道題確實有助于我鑒別應聘的人。但對于面試，畢竟還是要看面試者的綜合素質，一道（或幾道）題定生死不可取。

上一篇：基于C語言string函數的詳解

下一篇：如何在二叉樹中找出和為某一值的所有路徑