出棧序列相對(duì)入棧序列關(guān)系

1、出棧序列相對(duì)入棧序列關(guān)系出棧序列相對(duì)入棧序列關(guān)系在數(shù)據(jù)結(jié)構(gòu)的定義里，棧是只允許一端進(jìn)行插入或刪除操作的線性表。人們總結(jié)簡(jiǎn)化為后進(jìn)先出原則。棧的定義給定以后引出了另一類問(wèn)題——出棧序列問(wèn)題。就是在給定一個(gè)入棧序列（如a1a2…an）的條件下，在進(jìn)棧操作時(shí)，允許出棧操作，來(lái)判斷一下哪些序列是可能的出棧序列，而哪些必不是出棧序列。當(dāng)然，前提是要保證要求判斷的序列里面的元素要與給定入棧序列里的元素一一映射。否則就沒(méi)有再往下判斷的必要了。對(duì)于這類

2、問(wèn)題一般的方法是在本子上畫(huà)表格模擬一個(gè)棧然后實(shí)際操作一下，看看哪些是可調(diào)度實(shí)現(xiàn)的，哪些是不可能實(shí)現(xiàn)的。這種方法是很不嚴(yán)謹(jǐn)?shù)?，而且工作量很大，?duì)于一個(gè)具有n個(gè)元素的入棧序列，它的出棧序列有(1(n1))C2nn種可能。如果n稍大一點(diǎn)，工作量會(huì)頗具規(guī)模。到這來(lái)，您也許會(huì)有點(diǎn)被忽悠了，其實(shí)給定一個(gè)如棧序列，a1a2……an，再給定出要判斷的出棧隊(duì)列aiajak……判斷他們是否匹配，很簡(jiǎn)單，用一個(gè)大小為n的數(shù)組模擬棧，以a1a2……an做輸入，

3、對(duì)照著要判斷的序列aiajak……，有目的的操作在線性時(shí)間內(nèi)就可以完成。只是這種操作人工來(lái)說(shuō)稍微麻煩一點(diǎn)罷了。對(duì)于人工做判斷，研究發(fā)現(xiàn)這類問(wèn)題是具有一般規(guī)律的。在此先給出這一定律的定義，然后舉幾個(gè)常見(jiàn)的應(yīng)用，最后給出證明。這一定律是：在給定入棧順序序列的前提下，對(duì)于其出棧序列里任意元素an，晚于其出棧且先于入棧的元素必須按入棧的逆序排列。先后幾個(gè)應(yīng)用實(shí)例：1.設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許出棧操作，則下面得不到的序

4、列為：A.fedcbaB.bcafedC.dcefbaD.cabdef答案是D.因?yàn)锳.B.C項(xiàng)都滿足規(guī)律，但D項(xiàng)里ab晚于c出棧且先于c入棧，它們的排列順序應(yīng)是ba。2.元素abcde依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留，可出棧，直到所有元素都出棧，則在所有可能出棧序列中，以元素d開(kāi)頭的序列個(gè)數(shù)是多少個(gè)？這一問(wèn)題是可以很方便用上面給的規(guī)律來(lái)解決。序列以元素d開(kāi)頭說(shuō)明根據(jù)棧的性質(zhì)，和aiajak三個(gè)元素分別在Sa和Sb里的位置關(guān)系

5、克制，為ak在棧頂時(shí)，aiaj一定在棧里，是aj比ai更靠近棧頂。根據(jù)Sb里akaiaj的位置關(guān)系知Sk是先出棧的如果ak出棧后，ai先于aj出棧，這與棧只允許在一端進(jìn)行插入或刪除的操作自相矛盾。充分性證明：對(duì)于序列Sa我們只關(guān)心其序列里各元素的對(duì)應(yīng)位置關(guān)系，不考慮其它屬性。為表述方便我們把元素a1a2a3…an1an對(duì)映抽象為123，…，n1n（數(shù)值越大，表示其排列越靠后，即入棧越晚）記為Sd。對(duì)于序列Sbx1x2x3…xn里面的元素