[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/>