查看匯總：2015軟件水平考試程序員精選題匯總

　　棧的push、pop序列

　　題目：輸入兩個整數(shù)序列。其中一個序列表示棧的push順序，判斷另一個序列有沒有可能是對應(yīng)的pop順序。為了簡單起見，我們假設(shè)push序列的任意兩個整數(shù)都是不相等的。

　　比如輸入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一個pop系列。因為可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，這樣得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。

　　分析：這到題除了考查對棧這一基本數(shù)據(jù)結(jié)構(gòu)的理解，還能考查我們的分析能力。

　　這道題的一個很直觀的想法就是建立一個輔助棧，每次push的時候就把一個整數(shù)push進入這個輔助棧，同樣需要pop的時候就把該棧的棧頂整數(shù)pop出來。

　　我們以前面的序列4、5、3、2、1為例。第一個希望被pop出來的數(shù)字是4，因此4需要先push到棧里面。由于push的順序已經(jīng)由push序列確定了，也就是在把4 push進棧之前，數(shù)字1，2，3都需要push到棧里面。此時棧里的包含4個數(shù)字，分別是1，2，3，4，其中4位于棧頂。把4 pop出棧后，剩下三個數(shù)字1，2，3。接下來希望被pop的是5，由于仍然不是棧頂數(shù)字，我們接著在push序列中4以后的數(shù)字中尋找。找到數(shù)字5后再一次push進棧，這個時候5就是位于棧頂，可以被pop出來。接下來希望被pop的三個數(shù)字是3，2，1。每次操作前都位于棧頂，直接pop即可。

　　再來看序列4、3、5、1、2。pop數(shù)字4的情況和前面一樣。把4 pop出來之后，3位于棧頂，直接pop。接下來希望pop的數(shù)字是5，由于5不是棧頂數(shù)字，我們到push序列中沒有被push進棧的數(shù)字中去搜索該數(shù)字，幸運的時候能夠找到5，于是把5 push進入棧。此時pop 5之后，棧內(nèi)包含兩個數(shù)字1、2，其中2位于棧頂。這個時候希望pop的數(shù)字是1，由于不是棧頂數(shù)字，我們需要到push序列中還沒有被push進棧的數(shù)字中去搜索該數(shù)字。但此時push序列中所有數(shù)字都已被push進入棧，因此該序列不可能是一個pop序列。

　　也就是說，如果我們希望pop的數(shù)字正好是棧頂數(shù)字，直接pop出棧即可;如果希望pop的數(shù)字目前不在棧頂，我們就到push序列中還沒有被push到棧里的數(shù)字中去搜索這個數(shù)字，并把在它之前的所有數(shù)字都push進棧。如果所有的數(shù)字都被push進棧仍然沒有找到這個數(shù)字，表明該序列不可能是一個pop序列。

　　相關(guān)推薦：

　　2015年軟考信息技術(shù)處理員考前知識點總結(jié)匯總

　　2015年軟件水平考試《程序員》提高練習(xí)題匯總

　　2015軟件水平考試《程序員》知識點總結(jié)匯總