# 栈和队列 ## 简介 栈的特点是后入先出  根据这个特点可以临时保存一些数据，之后用到依次再弹出来，常用于 DFS 深度搜索 队列一般常用于 BFS 广度搜索，类似一层一层的搜索 ## Stack 栈 [min-stack](https://leetcode-cn.com/problems/min-stack/) > 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 思路：用两个栈实现，一个最小栈始终保证最小值在顶部 ```go type MinStack struct { min []int stack []int } /** initialize your data structure here. */ func Constructor() MinStack { return MinStack{ min: make([]int, 0), stack: make([]int, 0), } } func (this *MinStack) Push(x int) { min := this.GetMin() if x < min { this.min = append(this.min, x) } else { this.min = append(this.min, min) } this.stack = append(this.stack, x) } func (this *MinStack) Pop() { if len(this.stack) == 0 { return } this.stack = this.stack[:len(this.stack)-1] this.min = this.min[:len(this.min)-1] } func (this *MinStack) Top() int { if len(this.stack) == 0 { return 0 } return this.stack[len(this.stack)-1] } func (this *MinStack) GetMin() int { if len(this.min) == 0 { return 1 << 31 } min := this.min[len(this.min)-1] return min } /** * Your MinStack object will be instantiated and called as such: * obj := Constructor(); * obj.Push(x); * obj.Pop(); * param_3 := obj.Top(); * param_4 := obj.GetMin(); */ ``` [evaluate-reverse-polish-notation](https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/) > **波兰表达式计算** > **输入:** ["2", "1", "+", "3", "*"] > **输出:** 9 > **解释:** ((2 + 1) \* 3) = 9 思路：通过栈保存原来的元素，遇到表达式弹出运算，再推入结果，重复这个过程 ```go func evalRPN(tokens []string) int { if len(tokens)==0{ return 0 } stack:=make([]int,0) for i:=0;i 给定一个经过编码的字符串，返回它解码后的字符串。 > s = "3[a]2[bc]", 返回 "aaabcbc". > s = "3[a2[c]]", 返回 "accaccacc". > s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef". 思路：通过栈辅助进行操作 ```go func decodeString(s string) string { if len(s) == 0 { return "" } stack := make([]byte, 0) for i := 0; i < len(s); i++ { switch s[i] { case ']': temp := make([]byte, 0) for len(stack) != 0 && stack[len(stack)-1] != '[' { v := stack[len(stack)-1] stack = stack[:len(stack)-1] temp = append(temp, v) } // pop '[' stack = stack[:len(stack)-1] // pop num idx := 1 for len(stack) >= idx && stack[len(stack)-idx] >= '0' && stack[len(stack)-idx] <= '9' { idx++ } // 注意索引边界 num := stack[len(stack)-idx+1:] stack = stack[:len(stack)-idx+1] count, _ := strconv.Atoi(string(num)) for j := 0; j < count; j++ { // 把字符正向放回到栈里面 for j := len(temp) - 1; j >= 0; j-- { stack = append(stack, temp[j]) } } default: stack = append(stack, s[i]) } } return string(stack) } ``` 利用栈进行 DFS 递归搜索模板 ```go boolean DFS(int root, int target) { Set visited; Stack s; add root to s; while (s is not empty) { Node cur = the top element in s; return true if cur is target; for (Node next : the neighbors of cur) { if (next is not in visited) { add next to s; add next to visited; } } remove cur from s; } return false; } ``` [binary-tree-inorder-traversal](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/) > 给定一个二叉树，返回它的*中序*遍历。 ```go // 思路：通过stack 保存已经访问的元素，用于原路返回 func inorderTraversal(root *TreeNode) []int { result := make([]int, 0) if root == nil { return result } stack := make([]*TreeNode, 0) for len(stack) > 0 || root != nil { for root != nil { stack = append(stack, root) root = root.Left // 一直向左 } // 弹出 val := stack[len(stack)-1] stack = stack[:len(stack)-1] result = append(result, val.Val) root = val.Right } return result } ``` [clone-graph](https://leetcode-cn.com/problems/clone-graph/) > 给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。 ```go func cloneGraph(node *Node) *Node { visited:=make(map[*Node]*Node) return clone(node,visited) } // 1 2 // 4 3 // 递归克隆，传入已经访问过的元素作为过滤条件 func clone(node *Node,visited map[*Node]*Node)*Node{ if node==nil{ return nil } // 已经访问过直接返回 if v,ok:=visited[node];ok{ return v } newNode:=&Node{ Val:node.Val, Neighbors:make([]*Node,len(node.Neighbors)), } visited[node]=newNode for i:=0;i 给定一个由  '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。 思路：通过深度搜索遍历可能性（注意标记已访问元素） ```go func numIslands(grid [][]byte) int { var count int for i:=0;i=1{ count++ } } } return count } func dfs(grid [][]byte,i,j int)int{ if i<0||i>=len(grid)||j<0||j>=len(grid[0]){ return 0 } if grid[i][j]=='1'{ // 标记已经访问过(每一个点只需要访问一次) grid[i][j]=0 return dfs(grid,i-1,j)+dfs(grid,i,j-1)+dfs(grid,i+1,j)+dfs(grid,i,j+1)+1 } return 0 } ``` [largest-rectangle-in-histogram](https://leetcode-cn.com/problems/largest-rectangle-in-histogram/) > 给定 _n_ 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 > 求在该柱状图中，能够勾勒出来的矩形的最大面积。 思路：求以当前柱子为高度的面积，即转化为寻找小于当前值的左右两边值  用栈保存小于当前值的左的元素  ```go func largestRectangleArea(heights []int) int { if len(heights) == 0 { return 0 } stack := make([]int, 0) max := 0 for i := 0; i <= len(heights); i++ { var cur int if i == len(heights) { cur = 0 } else { cur = heights[i] } // 当前高度小于栈，则将栈内元素都弹出计算面积 for len(stack) != 0 && cur <= heights[stack[len(stack)-1]] { pop := stack[len(stack)-1] stack = stack[:len(stack)-1] h := heights[pop] // 计算宽度 w := i if len(stack) != 0 { peek := stack[len(stack)-1] w = i - peek - 1 } max = Max(max, h*w) } // 记录索引即可获取对应元素 stack = append(stack, i) } return max } func Max(a, b int) int { if a > b { return a } return b } ``` ## Queue 队列 常用于 BFS 宽度优先搜索 [implement-queue-using-stacks](https://leetcode-cn.com/problems/implement-queue-using-stacks/) > 使用栈实现队列 ```go type MyQueue struct { stack []int back []int } /** Initialize your data structure here. */ func Constructor() MyQueue { return MyQueue{ stack: make([]int, 0), back: make([]int, 0), } } // 1 // 3 // 5 /** Push element x to the back of queue. */ func (this *MyQueue) Push(x int) { for len(this.back) != 0 { val := this.back[len(this.back)-1] this.back = this.back[:len(this.back)-1] this.stack = append(this.stack, val) } this.stack = append(this.stack, x) } /** Removes the element from in front of queue and returns that element. */ func (this *MyQueue) Pop() int { for len(this.stack) != 0 { val := this.stack[len(this.stack)-1] this.stack = this.stack[:len(this.stack)-1] this.back = append(this.back, val) } if len(this.back) == 0 { return 0 } val := this.back[len(this.back)-1] this.back = this.back[:len(this.back)-1] return val } /** Get the front element. */ func (this *MyQueue) Peek() int { for len(this.stack) != 0 { val := this.stack[len(this.stack)-1] this.stack = this.stack[:len(this.stack)-1] this.back = append(this.back, val) } if len(this.back) == 0 { return 0 } val := this.back[len(this.back)-1] return val } /** Returns whether the queue is empty. */ func (this *MyQueue) Empty() bool { return len(this.stack) == 0 && len(this.back) == 0 } /** * Your MyQueue object will be instantiated and called as such: * obj := Constructor(); * obj.Push(x); * param_2 := obj.Pop(); * param_3 := obj.Peek(); * param_4 := obj.Empty(); */ ``` 二叉树层次遍历 ```go func levelOrder(root *TreeNode) [][]int { // 通过上一层的长度确定下一层的元素 result := make([][]int, 0) if root == nil { return result } queue := make([]*TreeNode, 0) queue = append(queue, root) for len(queue) > 0 { list := make([]int, 0) // 为什么要取length？ // 记录当前层有多少元素（遍历当前层，再添加下一层） l := len(queue) for i := 0; i < l; i++ { // 出队列 level := queue[0] queue = queue[1:] list = append(list, level.Val) if level.Left != nil { queue = append(queue, level.Left) } if level.Right != nil { queue = append(queue, level.Right) } } result = append(result, list) } return result } ``` [01-matrix](https://leetcode-cn.com/problems/01-matrix/) > 给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。 > 两个相邻元素间的距离为 1 ```go // BFS 从0进队列，弹出之后计算上下左右的结果，将上下左右重新进队列进行二层操作 // 0 0 0 0 // 0 x 0 0 // x x x 0 // 0 x 0 0 // 0 0 0 0 // 0 1 0 0 // 1 x 1 0 // 0 1 0 0 // 0 0 0 0 // 0 1 0 0 // 1 2 1 0 // 0 1 0 0 func updateMatrix(matrix [][]int) [][]int { q:=make([][]int,0) for i:=0;i=0&&x=0&&y