stack_queue.md

栈和队列

简介

栈的特点是后入先出

根据这个特点可以临时保存一些数据，之后用到依次再弹出来，常用于 DFS 深度搜索

队列一般常用于 BFS 广度搜索，类似一层一层的搜索

Stack 栈

min-stack

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

思路：用两个栈实现，一个最小栈始终保证最小值在顶部

typeMinStackstruct {
min []intstack []int
}
/** initialize your data structure here. */funcConstructor() MinStack {
returnMinStack{
min: make([]int, 0),
stack: make([]int, 0),
}
}
func (this*MinStack) Push(xint) {
min:=this.GetMin()
ifx<min {
this.min=append(this.min, x)
} else {
this.min=append(this.min, min)
}
this.stack=append(this.stack, x)
}
func (this*MinStack) Pop() {
iflen(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 {
iflen(this.stack) ==0 {
return0
}
returnthis.stack[len(this.stack)-1]
}
func (this*MinStack) GetMin() int {
iflen(this.min) ==0 {
return1<<31
}
min:=this.min[len(this.min)-1]
returnmin
}
/** * 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

波兰表达式计算 > 输入:["2", "1", "+", "3", "*"] > 输出: 9

解释:((2 + 1) * 3) = 9

思路：通过栈保存原来的元素，遇到表达式弹出运算，再推入结果，重复这个过程

funcevalRPN(tokens []string) int {
iflen(tokens)==0{
return0
}
stack:=make([]int,0)
fori:=0;i<len(tokens);i++{
switchtokens[i]{
case"+","-","*","/":
iflen(stack)<2{
return-1
}
// 注意：a为被除数，b为除数b:=stack[len(stack)-1]
a:=stack[len(stack)-2]
stack=stack[:len(stack)-2]
varresultintswitchtokens[i]{
case"+":
result=a+bcase"-":
result=a-bcase"*":
result=a*bcase"/":
result=a/b
}
stack=append(stack,result)
default:
// 转为数字val,_:=strconv.Atoi(tokens[i])
stack=append(stack,val)
}
}
returnstack[0]
}

decode-string

给定一个经过编码的字符串，返回它解码后的字符串。 s = "3[a]2[bc]", 返回 "aaabcbc". s = "3[a2[c]]", 返回 "accaccacc". s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

思路：通过栈辅助进行操作

funcdecodeString(sstring) string {
iflen(s) ==0 {
return""
}
stack:=make([]byte, 0)
fori:=0; i<len(s); i++ {
switchs[i] {
case']':
temp:=make([]byte, 0)
forlen(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 numidx:=1forlen(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))
forj:=0; j<count; j++ {
// 把字符正向放回到栈里面forj:=len(temp) -1; j>=0; j-- {
stack=append(stack, temp[j])
}
}
default:
stack=append(stack, s[i])
}
}
returnstring(stack)
}

利用栈进行 DFS 递归搜索模板

booleanDFS(introot, inttarget) {
Set<Node>visited;
Stack<Node>s;
addroottos;
while (sisnotempty) {
Nodecur=thetopelementins;
returntrueifcuristarget;
for (Nodenext : theneighborsofcur) {
if (nextisnotinvisited) {
addnexttos;
addnexttovisited;
}
}
removecurfroms;
}
returnfalse;
}

binary-tree-inorder-traversal

给定一个二叉树，返回它的中序遍历。

// 思路：通过stack 保存已经访问的元素，用于原路返回funcinorderTraversal(root*TreeNode) []int {
result:=make([]int, 0)
ifroot==nil {
returnresult
}
stack:=make([]*TreeNode, 0)
forlen(stack) >0||root!=nil {
forroot!=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
}
returnresult
}

clone-graph

给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。

funccloneGraph(node*Node) *Node {
visited:=make(map[*Node]*Node)
returnclone(node,visited)
}
// 1 2// 4 3// 递归克隆，传入已经访问过的元素作为过滤条件funcclone(node*Node,visitedmap[*Node]*Node)*Node{
ifnode==nil{
returnnil
}
// 已经访问过直接返回ifv,ok:=visited[node];ok{
returnv
}
newNode:=&Node{
Val:node.Val,
Neighbors:make([]*Node,len(node.Neighbors)),
}
visited[node]=newNodefori:=0;i<len(node.Neighbors);i++{
newNode.Neighbors[i]=clone(node.Neighbors[i],visited)
}
returnnewNode
}

number-of-islands

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

思路：通过深度搜索遍历可能性（注意标记已访问元素）

funcnumIslands(grid [][]byte) int {
varcountintfori:=0;i<len(grid);i++{
forj:=0;j<len(grid[i]);j++{
ifgrid[i][j]=='1'&&dfs(grid,i,j)>=1{
count++
}
}
}
returncount
}
funcdfs(grid [][]byte,i,jint)int{
ifi<0||i>=len(grid)||j<0||j>=len(grid[0]){
return0
}
ifgrid[i][j]=='1'{
// 标记已经访问过(每一个点只需要访问一次)grid[i][j]=0returndfs(grid,i-1,j)+dfs(grid,i,j-1)+dfs(grid,i+1,j)+dfs(grid,i,j+1)+1
}
return0
}

largest-rectangle-in-histogram

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。

思路：求以当前柱子为高度的面积，即转化为寻找小于当前值的左右两边值

用栈保存小于当前值的左的元素

funclargestRectangleArea(heights []int) int {
iflen(heights) ==0 {
return0
}
stack:=make([]int, 0)
max:=0fori:=0; i<=len(heights); i++ {
varcurintifi==len(heights) {
cur=0
} else {
cur=heights[i]
}
// 当前高度小于栈，则将栈内元素都弹出计算面积forlen(stack) !=0&&cur<=heights[stack[len(stack)-1]] {
pop:=stack[len(stack)-1]
stack=stack[:len(stack)-1]
h:=heights[pop]
// 计算宽度w:=iiflen(stack) !=0 {
peek:=stack[len(stack)-1]
w=i-peek-1
}
max=Max(max, h*w)
}
// 记录索引即可获取对应元素stack=append(stack, i)
}
returnmax
}
funcMax(a, bint) int {
ifa>b {
returna
}
returnb
}

Queue 队列

常用于 BFS 宽度优先搜索

implement-queue-using-stacks

使用栈实现队列

typeMyQueuestruct {
stack []intback []int
}
/** Initialize your data structure here. */funcConstructor() MyQueue {
returnMyQueue{
stack: make([]int, 0),
back: make([]int, 0),
}
}
// 1// 3// 5/** Push element x to the back of queue. */func (this*MyQueue) Push(xint) {
forlen(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 {
forlen(this.stack) !=0 {
val:=this.stack[len(this.stack)-1]
this.stack=this.stack[:len(this.stack)-1]
this.back=append(this.back, val)
}
iflen(this.back) ==0 {
return0
}
val:=this.back[len(this.back)-1]
this.back=this.back[:len(this.back)-1]
returnval
}
/** Get the front element. */func (this*MyQueue) Peek() int {
forlen(this.stack) !=0 {
val:=this.stack[len(this.stack)-1]
this.stack=this.stack[:len(this.stack)-1]
this.back=append(this.back, val)
}
iflen(this.back) ==0 {
return0
}
val:=this.back[len(this.back)-1]
returnval
}
/** Returns whether the queue is empty. */func (this*MyQueue) Empty() bool {
returnlen(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(); */

二叉树层次遍历

funclevelOrder(root*TreeNode) [][]int {
// 通过上一层的长度确定下一层的元素result:=make([][]int, 0)
ifroot==nil {
returnresult
}
queue:=make([]*TreeNode, 0)
queue=append(queue, root)
forlen(queue) >0 {
list:=make([]int, 0)
// 为什么要取length？// 记录当前层有多少元素（遍历当前层，再添加下一层）l:=len(queue)
fori:=0; i<l; i++ {
// 出队列level:=queue[0]
queue=queue[1:]
list=append(list, level.Val)
iflevel.Left!=nil {
queue=append(queue, level.Left)
}
iflevel.Right!=nil {
queue=append(queue, level.Right)
}
}
result=append(result, list)
}
returnresult
}

01-matrix

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。 两个相邻元素间的距离为 1

// 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 0funcupdateMatrix(matrix [][]int) [][]int {
q:=make([][]int,0)
fori:=0;i<len(matrix);i++{
forj:=0;j<len(matrix[0]);j++{
ifmatrix[i][j]==0{
// 进队列point:=[]int{i,j}
q=append(q,point)
}else{
matrix[i][j]=-1
}
}
}
directions:=[][]int{{0,1},{0,-1},{-1,0},{1,0}}
forlen(q)!=0{
// 出队列point:=q[0]
q=q[1:]
for_,v:=rangedirections{
x:=point[0]+v[0]
y:=point[1]+v[1]
ifx>=0&&x<len(matrix)&&y>=0&&y<len(matrix[0])&&matrix[x][y]==-1{
matrix[x][y]=matrix[point[0]][point[1]]+1// 将当前的元素进队列，进行一次BFSq=append(q,[]int{x,y})
}
}
}
returnmatrix
}

总结

• 熟悉栈的使用场景
  • 后入先出，保存临时值
  • 利用栈 DFS 深度搜索
• 熟悉队列的使用场景
  • 利用队列 BFS 广度搜索

练习

• min-stack
• evaluate-reverse-polish-notation
• decode-string
• binary-tree-inorder-traversal
• clone-graph
• number-of-islands
• largest-rectangle-in-histogram
• implement-queue-using-stacks
• 01-matrix