Related: LeetCode 946 - Validate Stack Sequences
Problem: Given two integer sequences, one of which is the push sequence of a stack, please check whether the other sequence is a corresponding pop sequence or not.
Problem: Given two integer sequences, one of which is the push sequence of a stack, please check whether the other sequence is a corresponding pop sequence or not.
For example, if 1, 2, 3, 4, 5 is a push sequence, 4, 5, 3, 2, 1 is a corresponding pop sequence, but the sequence 4, 3, 5, 1, 2 is not.
Key Idea: SimulationAn intuitive thought on this problem is to create an auxiliary stack. We push the numbers in the first sequence one by one, and try to pop them out according to the order in the second sequence.
bool IsPopOrder(const int* pPush, const int* pPop, int nLength)
{
bool bPossible = false;
if(pPush != NULL && pPop != NULL && nLength > 0)
{
const int* pNextPush = pPush;
const int* pNextPop = pPop;
std::stack<int> stackData;
while(pNextPop - pPop < nLength)
{
// When the number to be popped is not on top of stack,
// push some numbers in the push sequence into stack
while(stackData.empty() || stackData.top() != *pNextPop)
{
// If all numbers have been pushed, break
if(pNextPush - pPush == nLength)
break;
stackData.push(*pNextPush);
pNextPush ++;
}
if(stackData.top() != *pNextPop)
break;
stackData.pop();
pNextPop ++;
}
if(stackData.empty() && pNextPop - pPop == nLength)
bPossible = true;
}
return bPossible;
}
Read full article from Coding Interview Questions: No. 21 - Push and Pop Sequences of Stacks