[TOC] ## 栈和队列 1. 栈：先进后出 2. 队列：先进先出 * 栈和队列都可以用链表或者数组来实现 * 数组实现：能快速随机访问存储的元素，通过下标`index`访问，支持随机访问，查询速度快，但存在元素在数组空间中大量移动的操作，增删效率低。 * 链表实现：只支持顺序访问，在某些遍历操作中查询速度慢，但增删元素快。 ## 栈 ### 数组栈 ArrayStack <details> <summary>main.go</summary> ``` package main import ( "fmt" "sync" ) type ArrayStack struct { array []string size uint mu sync.Mutex } func (a *ArrayStack) Push(str string){ a.mu.Lock() defer a.mu.Unlock() a.array=append(a.array,str) a.size++ } func (a *ArrayStack)Pop ()string{ a.mu.Lock() defer a.mu.Unlock() if a.size==0 { panic("size is zeor") } pop :=a.array[a.size-1] newarr :=make([]string,a.size-1,a.size-1) for k, _ := range newarr { newarr[k]=a.array[k] } a.array =newarr a.size-- return pop } func (a *ArrayStack)Peek()string{ a.mu.Lock() defer a.mu.Unlock() if a.size==0 { panic("array is empty") } return a.array[a.size-1] } func (a *ArrayStack) Size()int{ return int(a.size) } func (a *ArrayStack) IsEmpty()bool{ return a.size==0 } func main() { arrayStack := ArrayStack{} arrayStack.Push("cat") arrayStack.Push("dog") arrayStack.Push("hen") fmt.Println("size:", arrayStack.Size()) fmt.Println("pop:", arrayStack.Pop()) fmt.Println("pop:", arrayStack.Pop()) fmt.Println("size:", arrayStack.Size()) arrayStack.Push("drag") fmt.Println("pop:", arrayStack.Pop()) /** size: 3 pop: hen pop: dog size: 1 pop: drag */ } ``` </details> <br/> ### 链表栈 LinkStack <details> <summary>main.go</summary> ``` package main import ( "fmt" "sync" ) type LinkNode struct { Next *LinkNode Value string } type LinkStack struct { root *LinkNode size uint mu sync.Mutex } func (l *LinkStack) Push(str string){ l.mu.Lock() defer l.mu.Unlock() //根节点 if l.root == nil { l.root=&LinkNode{Next: nil,Value: str} }else{ //把新节点当作root preNoe := l.root l.root=&LinkNode{Next: preNoe,Value: str} } l.size++ } func (l *LinkStack) Pop()string{ l.mu.Lock() defer l.mu.Unlock() if l.size==0 { panic("LinkStack is empty") } //获取 root 节点 tmp:=l.root //上移节点 l.root=l.root.Next l.size-- return tmp.Value } func (l *LinkStack) Peek()string{ l.mu.Lock() defer l.mu.Unlock() if l.size == 0 { panic("LinkStack is empty") } return l.root.Value } func (l *LinkStack) Size()int{ return int(l.size) } func (l *LinkStack) IsEmpty()bool{ return l.size==0 } func main() { linkStack := new(LinkStack) linkStack.Push("cat") linkStack.Push("dog") linkStack.Push("hen") fmt.Println("size:", linkStack.Size()) fmt.Println("pop:", linkStack.Pop()) fmt.Println("pop:", linkStack.Pop()) fmt.Println("size:", linkStack.Size()) linkStack.Push("drag") fmt.Println("pop:", linkStack.Pop()) } ``` </details> <br/> ## 队列实现 ### 数组实现 <details> <summary>main.go</summary> ``` package main import ( "fmt" "sync" ) type ArrayQueue struct { array []string size uint mu sync.Mutex } func (a *ArrayQueue) Add(str string){ a.mu.Lock() defer a.mu.Unlock() a.array = append(a.array, str) a.size++ } func (a *ArrayQueue) Remove()string{ a.mu.Lock() defer a.mu.Unlock() if a.size == 0 { panic("ArrayQueue is empty") } str :=a.array[0] a.array=a.array[1:a.size-1] a.size-- return str } func (a *ArrayQueue) Size() int { return int(a.size) } func (a *ArrayQueue) IsEmpty() bool { return a.size==0 } func main() { queue := &ArrayQueue{} queue.Add("1") queue.Add("2") queue.Add("3") fmt.Printf("%+v\n", queue.Remove()) //1 fmt.Printf("%+v\n", queue.Remove()) //2 } ``` </details> <br/> ### 链表实现 <details> <summary>main.go</summary> ``` package main import ( "fmt" "sync" ) type LinkNode struct { next *LinkNode value string } type LinkQueue struct { root *LinkNode size uint mu sync.Mutex } func (l *LinkQueue) Add(str string) { l.mu.Lock() defer l.mu.Unlock() if l.root==nil { l.root=&LinkNode{next: nil,value: str} }else{ newNode :=&LinkNode{next: nil,value: str} nowNode :=l.root for nowNode.next!=nil { nowNode = nowNode.next } nowNode.next=newNode } l.size++ } func (l *LinkQueue) Remove() string { l.mu.Lock() defer l.mu.Unlock() if l.size == 0 { panic("LinkQueue is empty") } firstNode :=l.root l.root=l.root.next return firstNode.value } func (l *LinkQueue) Size() int { return int(l.size) } func (l *LinkQueue) IsEmpty() bool { return l.size==0 } func main() { queue := &LinkQueue{} queue.Add("1") queue.Add("2") queue.Add("3") fmt.Printf("size :%+v\n", queue.Size()) //size:3 fmt.Printf("%+v\n", queue.Remove()) // 1 fmt.Printf("%+v\n", queue.Remove()) //2 } ``` </details> <br/>