首页 > 代码库 > 栈 给定push序列，判断给定序列是否是pop序列 ~ 进！出！进！出！进！出！进进出出！累死我了……
栈 给定push序列，判断给定序列是否是pop序列 ~ 进！出！进！出！进！出！进进出出！累死我了……
题目：
输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。
比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。
解法：
当不知道怎么做时，先看看我们充满智慧的人是如何思考的。比如上面的例子，push序列叫A，pop序列叫B，找出B的第一个数字4在A中的位置，一下子就找到了（这里深深鄙视电脑没有我们的好视力），4在B中第一个表明先让1、2、3、4依次进栈，然后让4出栈，这样4就是第一个了。然后看B的第二个数5，再次用人类犀利的眼睛找到其在A中的位置，发现在4后面，没事，这表明继续把5进栈，再出栈。设想如果B的这一个不是5而是3呢？也是可以的，只要出栈顶的就行。但是设想B的这个是1呢？那么不行了，因为1已经在栈底部了，不在栈的最表面。
从上面的分析，可以看到，我们只要确定B序列第一个数在A中的位置，从这个位置把A分成3部分，上面例子分成了123和4和5这三块，定义一个游标指向第一块的最后（如定义pST，那么它指向第一块的3），定义一个游标指向第三块的首个（如定义pRest，那么它指向第三块的5）。然后从B的第二个数开始，看它是不是和pST相等，相等说明这个数可以通过出栈得到，那么这个数出现在这个位置是没问题的；如果不等呢？那么看它与pRest是否相等，相等则表明这个数可以通过再进栈一个，然后出栈一个得到，那么这个数在这个位置也没有问题。若与pST和pRest都不等，那么这个数生错了位置，错。
其实也就是从中心向左右两边扩散，看是不是和边界的数相等。问题就这样转化了。代码：
1 #include <iostream> 2 #include <string> 3 4 using std::string; 5 using std::cin; 6 using std::cout; 7 using std::endl; 8 9 bool hs(const string& strSrc, const string& strJudge)10 {11 //先根据待比较字符串的首字母进行初始化12 int pPos = strSrc.find(strJudge[0]);13 int pST = -1, pRest = strSrc.length(); //两个游标14 if (pPos > 0)15 pST = pPos - 1;16 if (pPos < strSrc.length() - 1)17 pRest = pPos + 1;18 19 for (int ii = 1; ii < strSrc.length() - 1; ii++) //最后一个没必要管了20 {21 if (pST >=0 && strJudge[ii] == strSrc[pST]) //与栈顶的相同22 pST--;23 else if (pRest <= strSrc.length() - 1 && strJudge[ii] == strSrc[pRest]) //与剩下的第一个相同24 pRest++;25 else26 return false;27 }28 return true;29 }30 31 int main(void)32 {33 string strSrc("abcde");34 cout << hs(strSrc, "dceab");35 cin.get();36 }
栈 给定push序列，判断给定序列是否是pop序列 ~ 进！出！进！出！进！出！进进出出！累死我了……