typeStackstruct{st[]int}funcNewStack()*Stack{return&Stack{st:make([]int,0)}}func(s*Stack)Push(xint){s.st=append(s.st,x)}func(s*Stack)Peek()int{returns.st[len(s.st)-1]}func(s*Stack)Pop()int{n:=len(s.st)top:=s.st[n-1]s.st=s.st[:n-1]returntop}func(s*Stack)Empty()bool{returnlen(s.st)==0}

typeItemstruct{NumintOrderint}typeQueuestruct{items[]Item}funcNewQueue()*Queue{return&Queue{items:make([]Item,0),}}func(q*Queue)Push(xItem){q.items=append(q.items,x)}func(q*Queue)Pop()Item{x:=q.items[0]q.items=q.items[1:]returnx}func(q*Queue)Front()Item{returnq.items[0]}func(q*Queue)End()Item{returnq.items[len(q.items)-1]}func(q*Queue)Empty()bool{returnlen(q.items)==0}

import("container/list""fmt")// 滑动窗口最大值typeDequestruct{ll*list.List}funcNewDeque()*Deque{return&Deque{ll:list.New()}}func(dq*Deque)PushFront(xint){dq.ll.PushFront(x)}func(dq*Deque)PushBack(xint){dq.ll.PushBack(x)}func(dq*Deque)Pop(){// remove backdq.ll.Remove(dq.ll.Back())}func(dq*Deque)PopFront(){// remove firstdq.ll.Remove(dq.ll.Front())}func(dq*Deque)Front()int{returndq.ll.Front().Value.(int)}func(dq*Deque)Back()int{returndq.ll.Back().Value.(int)}func(dq*Deque)Len()int{returndq.ll.Len()}

packagemainimport"fmt"// 测试链表。在 redigo 里边使用到了链表作为 pool 的实现typeIntListstruct{countint// front,back 分别指向第一个和最后一个 node，或者是 nil。front.prev back.next 都是空front,back*Node}// 链表节点typeNodestruct{next,prev*Node}func(l*IntList)Count()int{returnl.count}func(l*IntList)pushFront(node*Node){node.next=l.frontnode.prev=nilifl.count==0{// note when list is emptyl.back=node}else{l.front.prev=node}l.front=nodel.count++}func(l*IntList)popFront(){first:=l.frontl.count--ifl.count==0{l.front,l.back=nil,nil}else{first.next.prev=nill.front=first.next}first.next,first.prev=nil,nil// clear first}func(l*IntList)popBack(){last:=l.backl.count--ifl.count==0{l.front,l.back=nil,nil}else{last.prev.next=nill.back=last.prev}last.prev,last.next=nil,nil}func(l*IntList)Print(){cur:=l.frontforcur!=l.back{fmt.Println(cur)cur=cur.next}ifl.back!=nil{fmt.Println(l.back)}}

// Package main provides ...packagemainimport"fmt"// https://golangbyexample.com/trie-implementation-in-go/const(ALBHABET_SIZE=26)typenodestruct{childrens[ALBHABET_SIZE]*nodeisWordEndbool}typetriestruct{root*node}funcnewTrie()*trie{return&trie{root:&node{},}}func(t*trie)insert(wordstring){wordLength:=len(word)current:=t.rootfori:=0;i<wordLength;i++{idx:=word[i]-'a'ifcurrent.childrens[idx]==nil{current.childrens[idx]=&node{}}current=current.childrens[idx]}current.isWordEnd=true}func(t*trie)find(wordstring)bool{wordLength:=len(word)current:=t.rootfori:=0;i<wordLength;i++{idx:=word[i]-'a'ifcurrent.childrens[idx]==nil{returnfalse}current=current.childrens[idx]}ifcurrent.isWordEnd{returntrue}returnfalse}funcmain(){trie:=newTrie()words:=[]string{"zhang","wang","li","zhao"}fori:=0;i<len(words);i++{trie.insert(words[i])}toFind:=[]string{"zhang","wang","li","zhao","gong"}fori:=0;i<len(toFind);i++{c:=toFind[i]iftrie.find(c){fmt.Printf("word[%s] found in trie.\n",c)}else{fmt.Printf("word[%s] not found in trie\n",c)}}}

packagemainimport"container/list"typeLRUCachestruct{lis*list.Listmmap[int]*list.Elementcapacityint}// 包装成一个 structtypeKVstruct{KeyintValint}funcConstructor(capacityint)LRUCache{returnLRUCache{lis:list.New(),m:make(map[int]*list.Element),capacity:capacity,}}func(this*LRUCache)Get(keyint)int{ifele,ok:=this.m[key];ok{this.lis.MoveToFront(ele)returnele.Value.(*KV).Val}return-1}func(this*LRUCache)Put(keyint,valueint){ifele,ok:=this.m[key];ok{ele.Value.(*KV).Val=valuethis.lis.MoveToFront(ele)return}ele:=this.lis.PushFront(&KV{key,value})this.m[key]=ele// map 保存的是 节点信息ifthis.lis.Len()>this.capacity{back:=this.lis.Back()delete(this.m,back.Value.(*KV).Key)this.lis.Remove(back)}}

packagemainimport("container/list""fmt")// 按照 key 插入顺序遍历 map，类似 python collections.OrderedDict。注意不是 key 的字典序，而是插入顺序typeOrderedMapstruct{mmap[string]intmemap[string]*list.Elementll*list.List// 记录 key order}funcNewOrderedMap()*OrderedMap{return&OrderedMap{m:make(map[string]int),me:make(map[string]*list.Element),ll:list.New(),}}func(o*OrderedMap)Set(kstring,vint){if_,found:=o.m[k];!found{e:=o.ll.PushBack(k)o.me[k]=e}o.m[k]=v}func(o*OrderedMap)Exist(kstring)bool{_,found:=o.m[k]returnfound}func(o*OrderedMap)Get(kstring)int{returno.m[k]}func(o*OrderedMap)Delete(kstring){delete(o.m,k)node:=o.me[k]o.ll.Remove(node)delete(o.me,k)}func(o*OrderedMap)Len()int{returnlen(o.m)}// 按照 key 进入顺序返回func(o*OrderedMap)Keys()[]string{keys:=make([]string,o.ll.Len())i:=0fore:=o.ll.Front();e!=nil;e=e.Next(){keys[i]=e.Value.(string)i++}returnkeys}

// This example demonstrates an integer heap built using the heap interface.// A heap is a tree with the property that each node is the minimum-valued node in its subtree.// 可以用来实现优先级队列 priority queuepackagemainimport("container/heap""fmt")// An IntHeap is a min-heap of ints.typeIntHeap[]intfunc(hIntHeap)Len()int{returnlen(h)}func(hIntHeap)Less(i,jint)bool{returnh[i]<h[j]}func(hIntHeap)Swap(i,jint){h[i],h[j]=h[j],h[i]}// 最后追加一个元素func(h*IntHeap)Push(xinterface{}){// Push and Pop use pointer receivers because they modify the slice's length,// not just its contents.*h=append(*h,x.(int))}// 移除并且返回最后一个元素func(h*IntHeap)Pop()interface{}{old:=*hn:=len(old)x:=old[n-1]*h=old[0:n-1]returnx}// This example inserts several ints into an IntHeap, checks the minimum,// and removes them in order of priority.funcmain(){h:=&IntHeap{2,1,5}heap.Init(h)fmt.Println(h)heap.Push(h,3)fmt.Println(h)fmt.Printf("minimum: %d\n",(*h)[0])// h[0] 最小的元素forh.Len()>0{fmt.Printf("%d ",heap.Pop(h))}}