前言
C++耍贾、java等語言都實現(xiàn)了棧阅爽、堆、隊列荐开、優(yōu)先級隊列等付翁。但是Go語言卻沒有。我們在實際使用中卻是需要這些基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)晃听，怎么辦百侧？自己造！
heap && priority_queue
go語言有標(biāo)準(zhǔn)容器庫 "container/heap"能扒，我們可以根據(jù)這個庫來實現(xiàn)堆以及優(yōu)先級隊列：
先看 "container/heap" 里的定義：
type Interface interface {
sort.Interface
Push(x interface{}) // add x as element Len()
Pop() interface{} // remove and return element Len() - 1.
}
這個堆使用的數(shù)據(jù)結(jié)構(gòu)是最小二叉樹佣渴，即根節(jié)點比左邊子樹和右邊子樹的所有值都小，其中 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)
}
所以要實現(xiàn)這五個接口就可以了~初斑，話不多說辛润，開干!
實現(xiàn)堆
// intHeap 實現(xiàn)了 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
}
實現(xiàn)優(yōu)先級隊列
package kit
import (
"container/heap"
)
//以下實現(xiàn)優(yōu)先級隊列
// 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 中取出最優(yōu)先的 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結(jié)構(gòu)實現(xiàn)棧和隊列
棧
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 中取出最先進(jìn)入隊列的值
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包來操作棧、隊列测摔、堆以及優(yōu)先級隊列在我們的代碼里了~ 是不是超簡單~
