一個棧的輸入序列為1 2 3 4 5 的出站順序的理解

一個棧的輸入序列為1 2 3 4 5 的出站順序是什么？

這個經(jīng)常會在面試的時(shí)候出現(xiàn)。如何判斷棧的進(jìn)出問題一個棧的輸入序列為1 2 3 4 5,則下列序列中不可能是棧的輸出序列的是( )A. 2 3 4 1

解答：

一個棧的輸入序列為1 2 3 4 5,則下列序列中不可能是棧的輸出序列的是( )

A.2 3 4 1 5 B.5 4 1 3 2C.2 3 1 4 5 D.1 5 4 3 2

這題就選B這樣的題做多了就找出規(guī)律了先進(jìn)1和2,2出棧進(jìn)入3,3出棧,進(jìn)入4,4出棧,1在出棧,5進(jìn),5出棧,所以是23415,A對進(jìn)1和2,2出棧進(jìn)入3,3出棧,進(jìn)入4,在進(jìn)入5,5出,4在出,就是23145,C對1進(jìn),1出,2345進(jìn),然后5432出,就是15432,D對B是錯誤,因?yàn)?要想出來,就必須五個數(shù)都要進(jìn)棧,那么出來就一種結(jié)果是54321,答案是54132所以不對這種題找規(guī)律,就能做出來我們都知道棧是先進(jìn)后出的，可以理解為桶狀結(jié)構(gòu)，對于上面那種不可能的情況可按下圖理解：5最先出來說明其他的四個都沒有出來，那么這四個的順序就必須安照進(jìn)來的先后順序依次排列，這就要符合先進(jìn)后出的原理，出來只有一個通道，下面的數(shù)字必須在后面才能出來。