Given the push and pop sequence on stack, verify if corresponding sequence is correct 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. 

Example

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.

Solution

An 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.
Take the sequence 4, 5, 3, 2, 1 as an example to analyze the process to push and pop. The first number to be popped is 4, so we need to push it into a stack. The pushing order is defined in the first sequence, where there are numbers 1, 2 and 3 prior to 4. Therefore, numbers 1, 2, and 3 are pushed into a stack before 4 is pushed. At this time, there are 4 numbers in a stack, which are 1, 2, 3 and 4, with 4 on top. When 4 is popped, numbers 1, 2 and 3 are left. The next number to be popped is 5, which is not on top of stack, so we have to push numbers in the first sequence into stack until 5 is pushed. When number 5 is on top of a stack, we can pop it. The next three numbers to be popped are 3, 2 and 1. Since these numbers are on top of a stack before pop operations, they can be popped directly. The whole process to push and pop is summarized in Table 1.

Step	Operation	Stack Status	Popped	Step	Operation	Stack Status	Popped
1	Push 1	1		6	Push 5	1, 2, 3, 5
2	Push 2	1, 2		7	Pop	1, 2, 3	5
3	Push 3	1, 2, 3		8	Pop	1, 2	3
4	Push 4	1, 2, 3, 4		9	Pop	1	2
5	Pop	1, 2, 3	4	10	Pop		1

Table 1: The process to push and pop with a push sequence 1, 2, 3, 4, 5 and pop sequence 4, 5, 3, 2, 1 Let us continue to analyze another pop sequence 4, 3, 5, 1, 2. The process to pop the first number 4 is similar to the process above. After the number 4 is popped, 3 is on the top of stack and it can be popped. The next number to be popped is 5. Since it is not on top, we have to push numbers in the first sequence until the number 5 is pushed. The number 5 can be popped when it is pushed onto the top of a stack. After 5 is popped out, there are only two numbers 1 and 2 left in stack. The next number to be popped is 1, but it is not on the top of stack. We have to push numbers in the first sequence until 1 is pushed. However, all numbers in the first sequence have been pushed. Therefore, the sequence 4, 3, 5, 1, 2 is not a pop sequence of the stack with push sequence 1, 2, 3, 4, 5. The whole process to push and pop is summarized in Table 2.

Step	Operation	Stack Status	Popped	Step	Operation	Stack Status	Popped
1	Push 1	1		6	Pop	1, 2	3
2	Push 2	1, 2		7	Push 5	1, 2, 5
3	Push 3	1, 2, 3		8	Pop	1, 2	5
4	Push 4	1, 2, 3, 4		The next number to be popped is 1, which is neither on the top of stack, nor in the remaining numbers of push sequence.
5	Pop	1, 2, 3	4

Table 1: The process to push and pop with a push sequence 1, 2, 3, 4, 5 and pop sequence 4, 3, 5, 1, 2 According to the analysis above, we get a solution to check whether a sequence is a pop sequence of a stack or not. If the number to be popped is currently on top of stack, just pop it. If it is not on the top of stack, we have to push remaining numbers into the auxiliary stack until we meet the number to be popped. If the next number to be popped is not remaining in the push sequence, it is not a pop sequence of a stack. The following is some sample code based on this solution:

 private static ArrayList<Integer> getListFromArr(int[] arr){
  ArrayList<Integer> aL = new ArrayList<>();
  for(int i: arr)
  {
   aL.add(i);
  }
  return aL;
 }

 public static boolean IsPopOrder(int[] pPush, int[] pPop)
 {
  if(pPush==null || pPop==null || (pPush.length<pPop.length))
   return false;
  
  boolean bPossible = false;
  int nLength = pPop.length;
  
  
  
  Stack <Integer> stackData = new Stack<Integer>();
  ArrayList<Integer> pNextPush =getListFromArr(pPush);  
  ArrayList<Integer> pNextPop = getListFromArr(pPop);


  int i = 0; //iterator on push list
  int j = 0; // iterator on pop list


  while(j < 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.peek() != pNextPop.get(j))
   {
    //push list is empty initially
    if(stackData.empty() && pNextPush.size()==0)
     break;
    else if(i < pNextPush.size()){
     stackData.push(pNextPush.get(i++));
    }
    // If all numbers have been pushed, break
    if(i == nLength)
     break;                   

   }
   out.println(stackData.toString());

   if(j<pNextPop.size())
    if(stackData.peek() != pNextPop.get(j))
     break;
   
   stackData.pop();
   j ++;
  }

  if(stackData.empty() && j == nLength)
   bPossible = true;


  return bPossible;
 }

References

• http://codercareer.blogspot.in/2011/11/no-21-push-and-pop-sequences-of-stacks.html