用兩個棧（Stack）實現(xiàn)一個隊列（Queue）-創(chuàng)新互聯(lián)

用C++描述，題目大致是這樣的：
 
已知下面Stack類及其3個方法Push、Pop和 Count，請用2個Stack實現(xiàn)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;
…
};

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

發(fā)展壯大離不開廣大客戶長期以來的信賴與支持，我們將始終秉承“誠信為本、服務(wù)至上”的服務(wù)理念，堅持“二合一”的優(yōu)良服務(wù)模式，真誠服務(wù)每家企業(yè)，認真做好每個細節(jié)，不斷完善自我，成就企業(yè)，實現(xiàn)共贏。行業(yè)涉及成都混凝土泵車等，在重慶網(wǎng)站建設(shè)公司、營銷型網(wǎng)站建設(shè)、WAP手機網(wǎng)站、VI設(shè)計、軟件開發(fā)等項目上具有豐富的設(shè)計經(jīng)驗。

入隊時，將元素壓入s1。

出隊時，將s1的元素逐個“倒入”（彈出并壓入）s2，將s2的頂元素彈出作為出隊元素，之后再將s2剩下的元素逐個“倒回”s1。

見下面示意圖：

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

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

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

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

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

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

真正性能較高的，其實是另一個變種。即：

入隊時，將元素壓入s1。

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

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

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)站標題：用兩個棧（Stack）實現(xiàn)一個隊列（Queue）-創(chuàng)新互聯(lián)
分享URL：http://muchs.cn/article6/dgioog.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、網(wǎng)站營銷、網(wǎng)站制作、企業(yè)網(wǎng)站制作、面包屑導(dǎo)航、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)