# 栈和队列
## 简介
栈的特点是后入先出
根据这个特点可以临时保存一些数据，之后用到依次再弹出来，常用于 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