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

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

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

解答：

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