Coding Interview Questions: No. 21 - Push and Pop Sequences of Stacks

Coding Interview Questions: No. 21 - Push and Pop Sequences of Stacks

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.

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.

http://www.shuatiblog.com/blog/2015/01/26/Push-and-Pop-Sequences-Stacks/

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;
}

http://tech-wonderland.net/blog/interview-question-6-validate-pop-sequence-of-stack.html
Read full article from Coding Interview Questions: No. 21 - Push and Pop Sequences of Stacks