|
判断一个序列是否为出栈序列 随着n的变大出栈序列总数越来越多由文献[]和[]可知出栈序列的求解问题是一个NP问题所以判断一个序列是否为一个出栈序列更为重要在文献[]的传统算法中 根据栈的定理[]判断某一序列是否为出栈序列该定理是对于集合N={ …n}如果依次序 …n入栈设alaa…an是 …n的一个全排列则alaa…an为出栈序列的充要条件是对于任意的ai在它后面的且比它小的数是降序排列的由该定理推出结论 若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为则序列为出栈序列否则不是 将该算法替代算法中的相应部分称为改进后的算法从表可以看出改进后的算法在运行时间上比原算法大大缩短甚至比算法还要好 [] [] [] [] [] [] [] [] |
