题目:输入两个整数序列。其中一个序列表示栈的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序列。
//判断输入输出是否符合栈的规则 #include <iostream> #include <stack> using namespace std; bool isstack(int *pushstr,int *popstr,int length) { if (pushstr==nullptr||popstr==nullptr||length<=0) { return false; } bool ismstack=false; stack<int> stackdata;//辅助栈 int *m_nextpush=pushstr;//输入栈中的数据 int *m_nextpop=popstr;//输出栈中的数据 stackdata.push(*m_nextpush);//给辅助栈一个初值 while (m_nextpop-popstr<length) { //判断栈顶元素是否与输出数组中的数相等,不等的话则继续输入 while (*m_nextpop!=stackdata.top()) { if (m_nextpush-pushstr<length-1) { m_nextpush++; stackdata.push(*m_nextpush); } //输入数组已经全部输入进去 else { m_nextpush==nullptr; break; } } //若与栈顶元素相等,将栈顶元素pop出去,表示已经输出了一个数,输出数组指针+1,指向下一个输出的数, if (*m_nextpop==stackdata.top()) { stackdata.pop(); m_nextpop++; } else { break; } } //当输出数组中所有的数都已经输出后,辅助栈的为空时则是正确的 if (stackdata.empty()&&m_nextpop-popstr==length) { ismstack=true; } return ismstack; } int main() { int m_push[5]={1,2,3,4,5}; int m_pop[5]={4,5,3,2,1}; bool c=false; c=isstack(m_push,m_pop,5); if (c==true) { cout<<"Yes"<<endl; } else { cout<<"No"<<endl; } return 0; }