前言
C++、java等语言都实现了栈、堆、队列、优先级队列等。但是Go语言却没有。我们在实际使用中却是需要这些基础数据结构，怎么办？自己造！
heap && priority_queue
go语言有标准容器库 "container/heap"，我们可以根据这个库来实现堆以及优先级队列：
先看 "container/heap" 里的定义：
type Interface interface {
sort.Interface
Push(x interface{}) // add x as element Len()
Pop() interface{} // remove and return element Len() - 1.
}
这个堆使用的数据结构是最小二叉树，即根节点比左边子树和右边子树的所有值都小，其中 sort.Interface的定义如下：
type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less reports whether the element with
// index i should sort before the element with index j.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}
所以要实现这五个接口就可以了~，话不多说，开干!
实现堆
// intHeap 实现了 heap 的接口
package kit
import (
"container/heap"
)
type intHeap []int
func (h intHeap) Len() int {
return len(h)
}
func (h intHeap) Less(i, j int) bool {
return h[i] < h[j]
}
func (h intHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *intHeap) Push(x interface{}) {
// Push 使用 *h，是因为
// Push 增加了 h 的长度
*h = append(*h, x.(int))
}
func (h *intHeap) Pop() interface{} {
// Pop 使用 *h ，是因为
// Pop 减短了 h 的长度
res := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return res
}
实现优先级队列
package kit
import (
"container/heap"
)
//以下实现优先级队列
// This example demonstrates a priority queue built using the heap interface.
// entry 是 priorityQueue 中的元素
type entry struct {
key string
priority int
// index 是 entry 在 heap 中的索引号
// entry 加入 Priority Queue 后， Priority 会变化时，很有用
// 如果 entry.priority 一直不变的话，可以删除 index
index int
}
// PQ implements heap.Interface and holds entries.
type PQ []*entry
func (pq PQ) Len() int { return len(pq) }
func (pq PQ) Less(i, j int) bool {
return pq[i].priority < pq[j].priority
}
func (pq PQ) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}
// Push 往 pq 中放 entry
func (pq *PQ) Push(x interface{}) {
temp := x.(*entry)
temp.index = len(*pq)
*pq = append(*pq, temp)
}
// Pop 从 pq 中取出最优先的 entry
func (pq *PQ) Pop() interface{} {
temp := (*pq)[len(*pq)-1]
temp.index = -1 // for safety
*pq = (*pq)[0 : len(*pq)-1]
return temp
}
// update modifies the priority and value of an entry in the queue.
func (pq *PQ) update(entry *entry, value string, priority int) {
entry.key = value
entry.priority = priority
heap.Fix(pq, entry.index)
}
stack && queue
采用go里的slice结构实现栈和队列
栈
package kit
// Stack 是用于存放 int 的 栈
type Stack struct {
nums []int
}
// NewStack 返回 *kit.Stack
func NewStack() *Stack {
return &Stack{nums: []int{}}
}
// Push 把 n 放入 栈
func (s *Stack) Push(n int) {
s.nums = append(s.nums, n)
}
// Pop 从 s 中取出最后放入 栈 的值
func (s *Stack) Pop() int {
res := s.nums[len(s.nums)-1]
s.nums = s.nums[:len(s.nums)-1]
return res
}
// Len 返回 s 的长度
func (s *Stack) Len() int {
return len(s.nums)
}
// IsEmpty 反馈 s 是否为空
func (s *Stack) IsEmpty() bool {
return s.Len() == 0
}
队列
package kit
// Queue 是用于存放 int 的队列
type Queue struct {
nums []int
}
// NewQueue 返回 *kit.Queue
func NewQueue() *Queue {
return &Queue{nums: []int{}}
}
// Push 把 n 放入队列
func (q *Queue) Push(n int) {
q.nums = append(q.nums, n)
}
// Pop 从 q 中取出最先进入队列的值
func (q *Queue) Pop() int {
res := q.nums[0]
q.nums = q.nums[1:]
return res
}
// Len 返回 q 的长度
func (q *Queue) Len() int {
return len(q.nums)
}
// IsEmpty 反馈 q 是否为空
func (q *Queue) IsEmpty() bool {
return q.Len() == 0
}
好啦，这样我们就可以直接使用自定义的kit包来操作栈、队列、堆以及优先级队列在我们的代码里了~ 是不是超简单~
