出棧序列相對入棧序列關系

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

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

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

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

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