栈 / 队列
最后更新于：2022-04-02 04:22:02
[TOC]
## 栈和队列
1. 栈：先进后出
2. 队列：先进先出
* 栈和队列都可以用链表或者数组来实现
* 数组实现：能快速随机访问存储的元素，通过下标`index`访问，支持随机访问，查询速度快，但存在元素在数组空间中大量移动的操作，增删效率低。
* 链表实现：只支持顺序访问，在某些遍历操作中查询速度慢，但增删元素快。
## 栈
### 数组栈 ArrayStack
### 链表栈 LinkStack
## 队列实现 ### 数组实现
### 链表实现
';
main.go
``` 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 */ } ```### 链表栈 LinkStack
main.go
``` 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()) } ```## 队列实现 ### 数组实现
main.go
``` 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 } ```### 链表实现