2.3 如何翻轉(zhuǎn)棧的所有元素

【出自ALBB面試題】

難度系數(shù)：★★★★☆

被考察系數(shù)：★★★★☆

題目描述：

翻轉(zhuǎn)（也叫顛倒）棧的所有元素，如輸入棧{1, 2, 3, 4, 5}。其中，1處在棧頂，翻轉(zhuǎn)之后的棧為{5, 4, 3, 2, 1}，5處在棧頂。

分析與解答：

最容易想到的辦法是，申請(qǐng)一個(gè)額外的隊(duì)列，先把棧中的元素依次出棧放到隊(duì)列里，然后把隊(duì)列里的元素按照出隊(duì)列順序入棧，這樣就可以實(shí)現(xiàn)棧的翻轉(zhuǎn)，這種方法的缺點(diǎn)是需要申請(qǐng)額外的空間存儲(chǔ)隊(duì)列，因此，空間復(fù)雜度較高。下面介紹一種空間復(fù)雜度較低的遞歸的方法。

遞歸程序有兩個(gè)關(guān)鍵因素需要注意：遞歸定義和遞歸終止條件。經(jīng)過分析后，很容易得到該問題的遞歸定義和遞歸終止條件。遞歸定義：將當(dāng)前棧的最底元素移到棧頂，其他元素順次下移一位，然后對(duì)不包含棧頂元素的子棧進(jìn)行同樣的操作。終止條件：遞歸下去，直到棧為空。遞歸的調(diào)用過程如下圖所示。

在上圖中，對(duì)于棧{1, 2, 3, 4, 5}，進(jìn)行翻轉(zhuǎn)的操作：首先把棧底元素移動(dòng)到棧頂?shù)玫綏5, 1, 2, 3, 4}，然后對(duì)不包含棧頂元素的子棧進(jìn)行遞歸調(diào)用（對(duì)子棧元素進(jìn)行翻轉(zhuǎn)），子棧{1, 2, 3, 4}翻轉(zhuǎn)的結(jié)果為{4, 3, 2, 1}，因此，最終得到翻轉(zhuǎn)后的棧為{5, 4, 3, 2, 1}。

此外，由于棧的后進(jìn)先出的特點(diǎn)，使得只能取棧頂?shù)脑兀虼耍褩５椎脑匾苿?dòng)到棧頂也需要遞歸調(diào)用才能完成。主要思路：把不包含該棧頂元素的子棧的棧底的元素移動(dòng)到子棧的棧頂，然后把棧頂?shù)脑嘏c子棧棧頂?shù)脑兀ㄆ鋵?shí)就是與棧頂相鄰的元素）進(jìn)行交換。

為了更容易理解遞歸調(diào)用，可以認(rèn)為在進(jìn)行遞歸調(diào)用時(shí)，子棧已經(jīng)把棧底元素移動(dòng)到了棧頂。在上圖中，為了把棧{1, 2, 3, 4, 5}的棧底元素5移動(dòng)到棧頂，首先對(duì)子棧{2, 3, 4, 5}，進(jìn)行遞歸調(diào)用，調(diào)用的結(jié)果為{5, 2, 3, 4}，然后對(duì)子棧頂元素5，與棧頂元素1進(jìn)行交換得到棧{5, 1, 2, 3, 4}，實(shí)現(xiàn)了把棧底元素移動(dòng)到了棧頂。

實(shí)現(xiàn)代碼如下：

程序的運(yùn)行結(jié)果為

算法性能分析：

把棧底元素移動(dòng)到棧頂操作的時(shí)間復(fù)雜度為O（N），在翻轉(zhuǎn)操作中對(duì)每個(gè)子棧都進(jìn)行了把棧底元素移動(dòng)到棧頂?shù)牟僮鳎虼耍D(zhuǎn)算法的時(shí)間復(fù)雜度為O（N^2）。

引申：如何給棧排序。

分析與解答：

很容易通過對(duì)上述方法進(jìn)行修改得到棧的排序算法。主要思路：首先對(duì)不包含棧頂元素的子棧進(jìn)行排序，如果棧頂元素大于子棧的棧頂元素，則交換這兩個(gè)元素。因此，在上述方法中，只需要在交換棧頂元素與子棧頂元素時(shí)增加一個(gè)條件判斷即可實(shí)現(xiàn)棧的排序。

實(shí)現(xiàn)代碼如下：

程序的運(yùn)行結(jié)果為

算法性能分析：

這種方法的時(shí)間復(fù)雜度為O（N^2）。