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

難度系數(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)過(guò)分析后，很容易得到該問(wèn)題的遞歸定義和遞歸終止條件。遞歸定義：將當(dāng)前棧的最底元素移到棧頂，其他元素順次下移一位，然后對(duì)不包含棧頂元素的子棧進(jìn)行同樣的操作。終止條件：遞歸下去，直到棧為空。遞歸的調(diào)用過(guò)程如下圖所示：

在上圖中，對(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ù)牟僮?，因此，翻轉(zhuǎn)算法的時(shí)間復(fù)雜度為O(n²)。

引申：如何給棧排序？

分析與解答：

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

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

算法性能分析：

這種方法的時(shí)間復(fù)雜度為O(n²)。