Interview Question 6: Validate Pop Sequence of Stack

Preface:

I wrote a program to automatically validate the pop sequence of stack in linear time to determine whether such pop sequence is possible or not given a specific push sequence.

Validate Pop Sequence of Stack Problem Definition:

The following is from coursera:

Suppose that an intermixed sequence of 10 push and 10 pop operations are performed on a LIFO stack. The pushes push the letters 0 through 9 in order; the pops print out the return value. Which of the following output sequence(s) could occur? Some of the examples are:

1) "1 0 2 3 4 7 6 5 9 8" is valid by the push/pop sequence of "0 1 - - 2 - 3 - 4 - 5 6 7 - - - 8 9 - -"
2) "0 2 1 3 4 6 9 8 7 5" is valid by the push/pop sequence of "0 - 1 2 - - 3 - 4 - 5 6 - 7 8 9 - - - - "
3) "3 2 4 6 1 8 7 9 5 0" is invalid because When 6 is pushed, both 1 and 5 are still on the stack. So, 5 would be popped before 1.
4) "4 3 2 1 0 5 6 7 8 9" is valid by the push/pop sequence of "0 1 2 3 4 - - - - - 5 - 6 - 7 - 8 - 9 - "
5) "1 2 4 0 3 5 6 8 7 9" is invalid because When 4 is pushed, both 0 and 3 are still on the stack. So, 3 would be popped before 0.

This question actually could be generalized into any two input sequences one for push, and one for pop, and the push sequence does not have to be increasing order, as you could see from the source code I wrote, it does not put any restrict on the number of pushes/pops or the order of the push sequence.

Validate Pop Sequence of Stack Solution Analysis:

1) To manually determine, you have to follow the following rules: for each number A in the pop sequence, you have to check all the number which are smaller A and yet not popped out, all such numbers have to be popped out in descending order, otherwise, it is an invalid pop sequence. You could verify the correctness by the example above.

2) To implement the rules in 1), you need O(N^2) time, but we actually could just simulate the whole intermixed sequence by the given push and pop sequence and check whether such simulation could be finished successfully, the following could passe all the test cases. Since every element in the push and pop sequence are accessed just once, it is linear to the number of push and pop sequence. That is, the time complexity is O(N);

bool validatePopStk(const std::vector<int>& vecPush, const std::vector<int>& vecPop) {
		if (vecPush.size() != vecPop.size()) return false;
		int nCount   = vecPush.size();
		auto itrPush = vecPush.begin(), itrPop  = vecPop.begin();
		std::stack<int> stk;
		while (itrPop != vecPop.end()) {
			if (stk.empty() || stk.top() != *itrPop) {
				while (itrPush != vecPush.end() && (stk.empty() || stk.top() != *itrPop )) {
					stk.push(*itrPush);
					++itrPush;
				}
				if (!stk.empty() && stk.top() != *itrPop) break;
			}
			else {
				stk.pop(), ++itrPop;
			}
		}
		return stk.empty() && itrPop == vecPop.end() && itrPush == vecPush.end();
}

Conclusion:

To summarize, analysis and implementations (in linear time) are given to determine whether or not a pop sequence of stack is possible given a specific push sequence.

 

(End. Original articles, please associate the author information and original URL with any reprints)


(Please specify the source  烟客旅人 sigmainfy — http://www.sigmainfy.com for any reprints,  

and please do not use it for commercial purpose)

</div>

Written on September 25, 2014