Stack Push and Pop Sequences

1. Problem Description

Given two integer sequences, the first sequence represents the push order of a stack. Determine whether the second sequence could be a pop order of that stack. Assume that all numbers pushed into the stack are distinct. For example, 1,2,3,4,5 is a push sequence. 4,5,3,2,1 is a possible corresponding pop sequence, while 4,3,5,1,2 is not. (Note: the two sequences have the same length.)

2. Approach

• Traverse pushV and push values into the stack, then check whether the stack elements match popV; pop when they match

3. Implementation

package main

/**
 * The class name, method name, and parameter names in the code have already been specified. Do not modify them; directly return the value required by the method.
 *
 * @param pushV one-dimensional int array
 * @param popV one-dimensional int array
 * @return bool
 */
// 1. Initialize pointer i to the first position of pushV and pointer j to the first position of popV
// 2. If pushV[i] != popV[j], push pushV[i] into the stack and ++i
// 3. Otherwise, pushV[i] == popV[j], meaning this element is popped immediately after being pushed, so ++i and ++j; then check whether popV[j] equals the stack top. If equal, ++j and pop the stack top
// 4. Repeat steps 2 and 3. If i == pushV.size(), the push sequence has been fully visited. Then check whether the stack is empty; if it is, the sequences match, otherwise they do not
func IsPopOrder(pushV []int, popV []int) bool {
	if len(pushV) == 0 && len(popV) == 0 {
		return true
	}

	if len(pushV) != len(popV) {
		return false
	}

	newStack := make([]int, 0)
	i := 0
	j := 0
	for i < len(pushV) {
		if pushV[i] != popV[j] {
			newStack = append(newStack, pushV[i])
			i++
		} else {
			i++
			j++
			for len(newStack) > 0 && newStack[len(newStack)-1] == popV[j] {
				newStack = newStack[:len(newStack)-1]
				j++
			}
		}
	}

	return len(newStack) == 0
}

func stackPush(stack *[]int, num int) {
	*stack = append(*stack, num)
}

func stackPop(stack *[]int) int {
	top := (*stack)[len(*stack)-1]
	*stack = (*stack)[:len(*stack)-1]
	return top
}

func stackEmpty(stack []int) bool {
	return len(stack) == 0
}
func stackTop(stack []int) int {
	return stack[len(stack)-1]
}

func IsPopOrder2(pushV []int, popV []int) bool {
	if len(pushV) != len(popV) {
		return false
	}

	if len(pushV) == 0 || len(popV) == 0 {
		return false
	}

	stack := make([]int, 0)

	i := 0
	for _, pushVal := range pushV {
		stackPush(&stack, pushVal)
		for !stackEmpty(stack) && stackTop(stack) == popV[i]{
			i++
			stackPop(&stack)
		}
	}

	return len(stack) == 0
}

func validateStackSequences(pushed []int, popped []int) bool {
    if len(pushed) != len(popped) {return false}
    var stack []int
    for _, val := range pushed {
        if val == popped[0] {
            popped = popped[1:]
        }else {
            for len(stack) > 0 && stack[len(stack)-1] == popped[0] {
                stack = stack[:len(stack)-1]
                popped = popped[1:]
            }
            stack = append(stack, val)
        }
    }
    for len(stack) > 0 && stack[len(stack)-1] == popped[0] {
        stack = stack[:len(stack)-1]
        popped = popped[1:]
    }
    return len(stack) == 0
}

4. References

• Stack Push and Pop Sequences - NowCoder
• Sword Offer 31. Stack Push and Pop Sequences - LeetCode