队列.md

队列

实现

232. 用栈实现队列

type MyQueue struct {
    Stack []int
    HelpStack []int
}


func Constructor() MyQueue {
    return MyQueue{}
}


func (this *MyQueue) Push(x int)  {
    this.Stack = append(this.Stack, x)
}


func (this *MyQueue) Pop() int {
    for len(this.Stack) > 0 {
        top := this.Stack[len(this.Stack)-1]
        this.Stack = this.Stack[:len(this.Stack)-1]
        this.HelpStack = append(this.HelpStack, top)
    }
    x := this.HelpStack[len(this.HelpStack)-1]
    this.HelpStack = this.HelpStack[:len(this.HelpStack)-1]
    for len(this.HelpStack) > 0 {
        top := this.HelpStack[len(this.HelpStack)-1]
        this.HelpStack = this.HelpStack[:len(this.HelpStack)-1]
        this.Stack = append(this.Stack, top)
    }
    return x
}


func (this *MyQueue) Peek() int {
    for len(this.Stack) > 0 {
        top := this.Stack[len(this.Stack)-1]
        this.Stack = this.Stack[:len(this.Stack)-1]
        this.HelpStack = append(this.HelpStack, top)
    }
    x := this.HelpStack[len(this.HelpStack)-1]
    for len(this.HelpStack) > 0 {
        top := this.HelpStack[len(this.HelpStack)-1]
        this.HelpStack = this.HelpStack[:len(this.HelpStack)-1]
        this.Stack = append(this.Stack, top)
    }
    return x
}


func (this *MyQueue) Empty() bool {
    return len(this.Stack) == 0
}

例子

542. 01 矩阵

func updateMatrix(mat [][]int) [][]int {
    queue := make([][]int, 0) 
    for i := 0; i < len(mat); i++ {
        for j := 0; j < len(mat[0]); j++ {
            if mat[i][j] == 0 {
                point := []int{i, j}
                queue = append(queue, point)
            } else {
                mat[i][j] = -1
            }          
        }
    }

    directions := [][]int{{0, 1}, {0, -1}, {-1, 0}, {1, 0}}
    for len(queue) > 0 {
        point := queue[0]
        queue = queue[1:]
        for _, direction := range directions {
            x := point[0] + direction[0]
            y := point[1] + direction[1]

            if x >= 0 && x < len(mat) && y >= 0 && y < len(mat[0]) && mat[x][y] == -1 {
                mat[x][y] = mat[point[0]][point[1]] + 1
                queue = append(queue, []int{x, y})
            }
        }
    }
    return mat
}