2.4 如何根據入棧序列判斷可能的出棧序列

【出自TX面試題】

難度系數：★★★☆☆

被考察系數：★★★★★

題目描述：

輸入兩個整數序列，其中一個序列表示棧的push（入）順序，判斷另一個序列有沒有可能是對應的pop（出）順序。

分析與解答：

假如輸入的push 序列是1、2、3、4、5，那么3、2、5、4、1 就有可能是一個pop 序列，但5、3、4、1、2 就不可能是它的一個pop 序列。

主要思路：使用一個棧來模擬入棧順序，具體步驟如下：

1）把push序列依次入棧，直到棧頂元素等于pop序列的第一個元素，然后棧頂元素出棧，pop序列移動到第二個元素。

2）如果棧頂繼續等于pop序列現在的元素，則繼續出棧并pop后移；否則對push序列繼續入棧。

3）如果push序列已經全部入棧，但是pop序列未全部遍歷，而且棧頂元素不等于當前pop元素，那么這個序列不是一個可能的出棧序列。如果棧為空，而且pop序列也全部被遍歷過，則說明這是一個可能的pop序列。下圖給出一個合理的pop序列的判斷過程。

在上圖中，（1）～（3）三步，由于棧頂元素不等于pop序列第一個元素3，因此，1，2， 3依次入棧，當3入棧后，棧頂元素等于pop序列的第一個元素3。因此，第（4）步執行3出棧，接下來指向第二個pop序列2，且棧頂元素等于pop序列的當前元素。第（5）步執行2出棧；接著由于棧頂元素4不等于當前pop序列5，因此接下來（6）和（7）兩步分別執行4和5入棧；接著由于棧頂元素5等于pop序列的當前值，第（8）步執行5出棧，接下來（9）和（10）兩步棧頂元素都等于當前pop 序列的元素。因此，都執行出棧操作。最后由于棧為空，同時pop序列都完成了遍歷，因此，{3,2,5,4,1}是一個合理的出棧序列。

實現代碼如下：

程序的運行結果為

算法性能分析：

這種方法在處理一個合理的pop序列的時候需要操作的次數最多，即把push序列進行一次壓棧和出棧操作，操作次數為2N。因此，時間復雜度為O（N）。此外，這種方法使用了額外的棧空間，因此，空間復雜度為O（N）。