C++用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列（面試官的小結(jié)）

前言

兩年前從網(wǎng)上看到一道面試題：用兩個(gè)棧（Stack）實(shí)現(xiàn)一個(gè)隊(duì)列（Queue）。覺得不錯(cuò)，就經(jīng)常拿來面試，幾年下來，做此題的應(yīng)該有幾十人了。通過對(duì)面試者的表現(xiàn)和反應(yīng)，有一些統(tǒng)計(jì)和感受，在此做個(gè)小結(jié)。

用C++描述，題目大致是這樣的：

已知下面Stack類及其3個(gè)方法Push、Pop和 Count，請(qǐng)用2個(gè)Stack實(shí)現(xiàn)Queue類的入隊(duì)(Enqueue)出隊(duì)(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;
…
};

這道題應(yīng)該不算難，比起《編程之美》中微軟那些什么“翻烙餅”的面試題，難度上差遠(yuǎn)了。況且，由于時(shí)間關(guān)系，我一般也不要求面試者寫代碼，只描述清楚思路即可。出這道題，主要考察3點(diǎn)：

1.       在短時(shí)間內(nèi)，能不能找到解決這道題的足夠清晰的思路（思維是否敏捷、清晰）。

2.       能不能在單向表述中，清楚地描述自己的思路和想法（表述能力是否達(dá)到要求）。

3.       對(duì)于某些具體細(xì)節(jié)，能不能考慮到（是否足夠細(xì)致）。

總體上，以10人為例，實(shí)際的結(jié)果大致是：

1.       8個(gè)人可以找到解決答案，2個(gè)人無法找到答案（即使進(jìn)行了必要的提示，曾經(jīng)有位號(hào)稱美國MIT深造2年，之后在Google美國公司工作過8個(gè)月的兄弟，也沒做出來）。

2.       8個(gè)找到答案的人中，6個(gè)找到的方法相同，2個(gè)人找到其它變種。

3.       在這8個(gè)人中，有1個(gè)人可以不經(jīng)提示，同時(shí)想到大眾方法和變種。

大多數(shù)人的思路是：始終維護(hù)s1作為存儲(chǔ)空間，以s2作為臨時(shí)緩沖區(qū)。

入隊(duì)時(shí)，將元素壓入s1。

出隊(duì)時(shí)，將s1的元素逐個(gè)“倒入”（彈出并壓入）s2，將s2的頂元素彈出作為出隊(duì)元素，之后再將s2剩下的元素逐個(gè)“倒回”s1。

見下面示意圖：

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

上述思路，有些變種，如：

入隊(duì)時(shí)，先判斷s1是否為空，如不為空，說明所有元素都在s1，此時(shí)將入隊(duì)元素直接壓入s1；如為空，要將s2的元素逐個(gè)“倒回”s1，再壓入入隊(duì)元素。

出隊(duì)時(shí)，先判斷s2是否為空，如不為空，直接彈出s2的頂元素并出隊(duì)；如為空，將s1的元素逐個(gè)“倒入”s2，把最后一個(gè)元素彈出并出隊(duì)。

有些人能同時(shí)想到大眾方法和變種，應(yīng)該說頭腦還是比較靈光的。

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

真正性能較高的，其實(shí)是另一個(gè)變種。即：

入隊(duì)時(shí)，將元素壓入s1。

出隊(duì)時(shí)，判斷s2是否為空，如不為空，則直接彈出頂元素；如為空，則將s1的元素逐個(gè)“倒入”s2，把最后一個(gè)元素彈出并出隊(duì)。

這個(gè)思路，避免了反復(fù)“倒”棧，僅在需要時(shí)才“倒”一次。但在實(shí)際面試中很少有人說出，可能是時(shí)間較少的緣故吧。

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

個(gè)人感覺，這道題確實(shí)有助于我鑒別應(yīng)聘的人。但對(duì)于面試，畢竟還是要看面試者的綜合素質(zhì)，一道（或幾道）題定生死不可取。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對(duì)億速云的支持。