Question

link

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.

Solution

Refer to this answer:

Construct the stack:

For each number X in the pop order:

If this number is not the same as the top of the stack (or the stack is empty),
push numbers from the push order until you pushed X.

If you pushed all numbers and didn't find X, there's no way to get the pop order.

Pop X

Code

public boolean validSequence(int[] input, int[] sequenc) {
	// keep a pointer p in the input[] array
	int len = input.length;
	int p = 0;
	Stack<Integer> stack = new Stack<Integer>();

	int i = 0;
	while (i < len) {
		if (stack.isEmpty()) {
			// just push an element to stack
			stack.push(input[p++]);
		} else {
			// stack got elements, then check top one
			if (stack.peek() == sequenc[i]) {
				// seq found, proceed to next number in seq
				stack.pop();
				i++;
			} else {
				// did not find seq, keep pushing to stack until done
				if (p == len) {
					return false;
				} else {
					stack.push(input[p++]);
				}
			}
		}
	}
	return i == len; // or just return true;
}