算法题解3_栈的压入弹出序列

输入两个整数数列，第一个序列表示栈的压入顺序，判断第二个序列是否为该栈的弹出序列。假设压入栈的所有元素均不等。如序列 1，2，3，4，5是压入序列，则4，5，3，2，1可以是弹出序列，但是4，3，5，1，2就不能是弹出序列

解法

设定一个辅助栈，两个变量nextPop和nextPush分别指向弹出序列和压入序列的当前元素。如果nextPop指向的元素和栈顶元素一样，直接弹出；如果不等，把nextPush指向的和后面的元素压入栈，直到栈顶元素和nextPop指向元素相等。

代码如下：

public static boolean isPopPossible(int[] pushOrder, int[] popOrder) {
	
	boolean possible = false;
	
	if ( pushOrder == null || popOrder == null || pushOrder.length != popOrder.length )
		return false;
	
	int next_pop = 0;
	int next_push = 0;
	
	Stack<Integer> dataStack = new Stack<Integer>();
	
	while ( next_pop < popOrder.length ) {
		
		while ( dataStack.empty() || dataStack.peek() != popOrder[next_pop] ) {
			
			if ( pushOrder.length == next_push )
				break;
			
			dataStack.push( pushOrder[next_push++] );
		}
		
		if ( dataStack.peek() != popOrder[next_pop] )
			break;
		
		dataStack.pop();
		next_pop++;
		
	}
	
	if ( dataStack.empty() && next_pop == popOrder.length )
		possible = true;
	
	return possible;
}

Written on January 7, 2016