出棧序列的研究[7]

判斷一個序列是否為出棧序列

隨著n的變大出棧序列總數越來越多由文獻[]和[]可知出棧序列的求解問題是一個NP問題所以判斷一個序列是否為一個出棧序列更為重要在文獻[]的傳統算法中 根據棧的定理^[]判斷某一序列是否為出棧序列該定理是對於集合N={ …n}如果依次序 …n入棧設a_laa…a_n是 …n的一個全排列則a_laa…a_n為出棧序列的充要條件是對於任意的a_i在它後面的且比它小的數是降序排列的由該定理推出結論 若pqr是入棧序列中的數且p<q < r則出序序列中pqr的排列次序不可能是rpq 

由上述推論可設計出判斷某個序列是否為合法的出棧序列該算法的源代碼如下 

flag=l; // 沒標志為l假設序列a為合法的出棧序列

for(u=;u<=n;u++) 

for(v=u+;v<=n;v++) 

for(w=v+l;w<=n;w++) 

if((a[v]<a[w])&&(a[w]<a[u]))flag=; //若出棧次序為rpq則為不合法的出棧序列

該算法的時間復雜度為O(n)算法采用了該方法判斷某一序列是否為出棧序列其效率太低為此文中借助於棧實現復雜度為O(n)的算法其基本思想描述如下 

() 初始化棧stack設置flag為 

() v=w=v指要判斷的序列w指入棧的序列 

() 如果v > n或flag=則轉() 

() 如果棧stack是空棧則將第w個入棧序列符號人棧w++ 

() 如果stack棧頂元素值等於序列的第v個元素或者w ≤ n則轉() 

() 第w個入棧元素壓入stack棧中w ++轉() 

() 如果stack棧頂元素值等於序列的第v個元素則匹配stack棧頂元素出棧v++否則說明所判斷的序列不是出棧序列賦flag為零 

() 轉() 

() 結束若此時flag為則序列為出棧序列否則不是 

將該算法替代算法中的相應部分稱為改進後的算法從表可以看出改進後的算法在運行時間上比原算法大大縮短甚至比算法還要好

[]  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/22742.html