栈的压入弹出序列

1. 题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

2. 思路

• 遍历pushV压入栈中，然后看栈中的元素和popV是否匹配，匹配则出栈

3. 实现

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param pushV int整型一维数组
 * @param popV int整型一维数组
 * @return bool布尔型
 */
//1. 初始化：用指针i指向pushV的第一个位置， 指针j指向popV的第一个位置
//2. 如果pushV[i] != popV[j]， 那么应该将pushV[i]放入栈中， ++i
//3. 否则，pushV[i]==popV[j], 说明这个元素是放入栈中立马弹出，所以，++i, ++j，然后应该检查popV[j]与栈顶元素是否相等，如果相等，++j, 并且弹出栈顶元素
//4，重复2，3， 如果i==pushV.size(), 说明入栈序列访问完，此时检查栈是否为空，如果为空，说明匹配，斗则不匹配。
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. 参考

• 栈的压入、弹出序列_牛客题霸_牛客网
• 剑指 Offer 31. 栈的压入、弹出序列 - 力扣（LeetCode）