golang实现队列

╰半橙微兮° 2023-02-26 10:24 14阅读 0赞

## 基于环形缓冲区的双端队列实现 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

*  代码：

package main
    
    const minCapacity = 16
    
    type Deque struct {
        
    	buf []interface{
        }
    	head int
    	tail int
    	count int
    	minCap int
    }
    
    func NewDeque() *Deque  {
        
    	return &Deque{
        
    		buf:   make([]interface{
        }, minCapacity),
    		head:  0,
    		tail:  0,
    		count: 0,
    		minCap:minCapacity,
    	}
    }
    
    func (d *Deque) Len() int  {
        
    	return d.count
    }
    
    func (d *Deque) Empty() bool  {
        
    	return d.count == 0
    }
    
    // 尾部插入元素：从尾部插入元素，则tail需要改变
    func (d *Deque) PushBack(elem interface{
        })  {
        
    	d.groupIfFull()
    	
    	d.buf[d.tail] = elem
    	d.tail = d.next(d.tail)  // 计算新的尾部位置
    	d.count++
    }
    
    // 头部插入元素: 从头部插入元素，则head需要改变
    func (d *Deque) PushFront(elem interface{
        }) {
        
    	d.groupIfFull()
    
    	d.head = d.pre(d.head)
    	d.buf[d.head] = elem
    	d.count++
    }
    
    
    
    // 扩大/缩小容量： 为元素的2倍
    func (d *Deque) resize()  {
        
    	newBuf := make([]interface{
        }, d.count << 1)
    	
    	if(d.tail > d.head){
        
    		copy(newBuf, d.buf[d.head:d.tail])
    	}else{
        
    		n := copy(newBuf, d.buf[d.head:])
    		copy(newBuf[n:], d.buf[:d.tail])
    	}
    	
    	d.head = 0
    	d.tail = d.count   // 下一个尾部插入元素的索引位置
    	d.buf = newBuf
    }
    
    // 大于最小容量 && 当前元素个数  <= 缓冲区容量大小/4
    func (d *Deque) shrinkIfExcess() {
        
    	if len(d.buf) > d.minCap && (d.count<<2) <= len(d.buf){
        
    		d.resize()
    	}
    }
    
    //prev返回环绕缓冲区的上一个缓冲区位置。
    func (d *Deque) pre(i int) int {
        
    	return (i - 1) & (len(d.buf) - 1)
    }
    
    // next返回环绕缓冲区的下一个缓冲区位置
    func (d *Deque) next(i int) int {
        
    	return (i + 1) & (len(d.buf) - 1)
    }
    
    
    // PopFront从队列前面删除并返回元素。如果队列为空则panic
    func (d *Deque) PopFront() interface{
        } {
        
    	if d.count <= 0 {
        
    		panic("deque: PopFront() called on empty queue")
    	}
    
    
    	ret := d.buf[d.head]  // 备份要删除的元素
    	d.buf[d.head] = nil  // 在要删除的那个位置写nil
    	d.head = d.next(d.head) // 重新计算新head的索引
    	d.count--              // 元素个数减少1
    
    	d.shrinkIfExcess()
    	return ret
    }
    
    //PopBack 从队列最后面删除并返回元素。如果队列为空则panic
    func (d *Deque) PopBack() interface{
        } {
        
    	if d.count <= 0 {
        
    		panic("deque: PopBack() called on empty queue")
    	}
    
    	d.tail = d.pre(d.tail)
    
    
    	ret := d.buf[d.tail]
    	d.buf[d.tail] = nil
    	d.count--
    
    	d.shrinkIfExcess()
    	return  ret
    }
    
    // Front 返回队首元素。如果队列为空则panic
    func (d *Deque) Front() interface{
        } {
        
    	if d.count <= 0 {
        
    		panic("deque: Front() called when empty")
    	}
    
    	return d.buf[d.head]
    }
    
    // Back 返回队尾元素。如果队列为空则panic
    func (d *Deque) Back() interface{
        } {
        
    	if d.count <= 0 {
        
    		panic("deque: Back() called when empty")
    	}
    
    	return d.buf[d.pre(d.tail)]
    }
    func (d *Deque) groupIfFull()  {
        
    	if(len(d.buf) == 0){
        
    		if(d.minCap == 0){
        
    			d.minCap = minCapacity
    		}
    
    		d.buf = make([]interface{
        }, d.minCap)
    		return
    	}
    
    	if(len(d.buf) == d.count){
        
    		d.resize()
    	}
    }
    
    //At返回队列中索引i处的元素，而不从队列中移除元素。
    //此方法只接受非负索引值。
    //At（0）表示第一个元素，与Front（）相同。
    //At（Len（）-1）表示最后一个元素，与Back（）相同。
    //如果索引无效，则panic。
    // At的目的是让Deque充当一个更通用的循环缓冲区，其中的项只添加到Deque的末尾，
    //也可以从Deque中的任何位置读取。考虑一个固定大小的循环日志缓冲区的情况：
    //一个新的条目被推到一端，当满的时候从另一端弹出最旧的条目。
    //缓冲区中的所有日志条目必须是可读的，而不改变缓冲区的内容。
    func (q *Deque) At(i int) interface{
        } {
        
    	if i < 0 || i >= q.count {
        
    		panic("deque: At() called with index out of range")
    	}
    	// bitwise modulus
    	return q.buf[(q.head+i)&(len(q.buf)-1)]
    }
    
    // Set设置索引i处的元素。Set与At（）具有相同的用途，但执行相反的操作。
    //索引i与At（）定义的索引相同。如果索引无效，则panic
    func (q *Deque) Set(i int, elem interface{
        }) {
        
    	if i < 0 || i >= q.count {
        
    		panic("deque: Set() called with index out of range")
    	}
    	// bitwise modulus
    	q.buf[(q.head+i)&(len(q.buf)-1)] = elem
    }
    
    
    // 清除将从队列中删除所有元素，但保留当前容量。
    //当在重用期间以高频重复使用队列以避免GC时，这很有用。
    //只要只添加项目，队列的大小就不会变小。只有当项目被移除时，队列的大小才会变小。
    func (q *Deque) Clear() {
        
    	// bitwise modulus
    	modBits := len(q.buf) - 1
    	for h := q.head; h != q.tail; h = (h + 1) & modBits {
        
    		q.buf[h] = nil
    	}
    	q.head = 0
    	q.tail = 0
    	q.count = 0
    }
    
    // 设置 最小容量 = 2^(minCapacityExp)
    func (q *Deque) SetMinCapacity(minCapacityExp uint) {
        
    	if 1<<minCapacityExp > minCapacity {
        
    		q.minCap = 1 << minCapacityExp
    	} else {
        
    		q.minCap = minCapacity
    	}
    }
    
    
    
    func main() {
        
    
    }

*  容量设置成2^n的幂好处？  
    任何一个数和2^n-1做&运算可以用在循环队列的数组中快速指针的位置。
    
     *  一个负数x和2^n-1做&运算相当于 2^n-1-|x|
     *  一个正数x和2^n-1做&运算相当于取余

func main() {
        
    	cap := 4
    	// tail
    	fmt.Println((0 + 1) & (cap - 1)) // 1   tail = 0时，后一个索引为1
    	fmt.Println((1 + 1) & (cap - 1)) // 2   tail = 1时，后一个索引为2
    	fmt.Println((2 + 1) & (cap - 1)) // 3   tail = 2 时，后一个索引为3
    	fmt.Println((3 + 1) & (cap - 1)) // 0   tail = 4 时，后一个索引为0
    
    	// head 的那个索引
    	fmt.Println((0 - 1) & (cap - 1)) // 3    head = 0时， 前一个索引是3
    	fmt.Println((1 - 1) & (cap - 1)) // 0    head = 1时， 前一个索引为0
    	fmt.Println((2 - 1) & (cap - 1)) // 1    head = 2时， 前一个索引为1
    	fmt.Println((3 - 1) & (cap - 1)) // 2    head = 3时， 前一个索引为2
    }

[https://github.com/gammazero/deque][https_github.com_gammazero_deque]  
[参考][Link 1]

## 优先队列 ##

### 版本一： 基于切片实现 ###

优先队列的本质是一个大根堆或者小根堆。 [如何构建一个堆][Link 2]  
优先队列 = 普通的单向队列 + 堆  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]

#### 基于切片的堆实现 ####

package main
    
    import (
    	"sync"
    )
    
    type HeapItem interface {
        
    	Less (than HeapItem) bool
    }
    
    
    type Heap struct {
        
    	sync.Mutex
    	data []HeapItem
    	min  bool  // 当前堆是不是最小堆
    }
    
    func NewHeapMin() *Heap {
        
    	return &Heap{
        
    		data: make([]HeapItem, 0),
    		min:  true,
    	}
    }
    
    func NewHeapMax() *Heap {
        
    	return &Heap{
        
    		data: make([]HeapItem, 0),
    		min:  false,
    	}
    }
    
    // 无论是沉底还是上升，都需要比较
    func (h *Heap) Less(a, b HeapItem) bool  {
        
    	if h.min {
        
    		return a.Less(b)
    	}else{
        
    		return b.Less(a)
    	}
    }
    
    
    // 让最上面的元素沉底
    func (h *Heap)ShiftDown()  {
        
    	parent := 0
    	leftchild := parent << 1 + 1
    	rightchild := parent << 1 + 2
    
    	for{
        
    		min := parent
    		if leftchild < h.Len() && h.Less(h.data[leftchild], h.data[min]) {
        
    			min = leftchild
    		}
    		if rightchild < h.Len() && h.Less(h.data[rightchild], h.data[min]) {
        
    			min = rightchild
    		}
    
    		if min == parent{
        
    			return
    		}
    
    		h.data[min], h.data[parent] = h.data[parent], h.data[min]
    		parent = min
    		leftchild = parent << 1 + 1
    		rightchild = parent << 1 + 2
    	}
    }
    
    // 将数组的最后一个元素放到正确的位置去
    func (h *Heap)ShiftUp()  {
        
    	index := h.Len()  - 1
    	parent := (index - 1) >> 1
    
    	for parent >= 0 && h.Less(h.data[index], h.data[parent]) {
          // 当前节点和父节点比较
    		h.data[parent], h.data[index] = h.data[index], h.data[parent]
    		index = parent
    		parent = (index - 1) >> 1
    	}
    }
    
    
    
    func (h *Heap)Empty() bool  {
        
    	return len(h.data) == 0
    }
    
    func (h *Heap) Len() int {
        
    	return len(h.data)
    }
    
    func (h *Heap) Insert(v HeapItem) {
        
    	h.Lock()
    	defer h.Unlock()
    
    	h.data = append(h.data, v)
    	h.ShiftUp()
    }
    
    func (h *Heap) Delete() HeapItem{
        
    	h.Lock()
    	h.Unlock()
    
    	if h.Len() == 0 {
        
    		return nil
    	}
    
    	var el, last HeapItem
    
    	el = h.data[0]
    	last = h.data[h.Len() - 1]
    
    	if h.Len() == 1 {
        
    		h.data = nil
    	}else{
        
    		h.data = append([]HeapItem{
        last}, h.data[1:h.Len()-1]...)
    		h.ShiftDown()
    	}
    
    	return el
    }

测试：

package main
    
    import (
    	"fmt"
    	"testing"
    )
    
    type Int int
    
    func (x Int) Less(than HeapItem) bool {
        
    	return x < than.(Int)
    }
    
    func TestMinHeap(t *testing.T) {
        
    	h := NewHeapMin()
    
    	h.Insert(Int(8))
    	h.Insert(Int(7))
    	h.Insert(Int(6))
    	h.Insert(Int(3))
    	h.Insert(Int(1))
    	h.Insert(Int(0))
    	h.Insert(Int(2))
    	h.Insert(Int(4))
    	h.Insert(Int(9))
    	h.Insert(Int(5))
    
    	sorted := make([]Int, 0)
    	for h.Len() > 0 {
        
    		sorted = append(sorted, h.Delete().(Int))
    	}
    
    	for i := 0; i < len(sorted)-2; i++ {
        
    		if sorted[i] > sorted[i+1] {
        
    			fmt.Println(sorted)
    			t.Error()
    		}
    	}
    }
    
    func TestMaxHeap(t *testing.T) {
        
    	h := NewHeapMax()
    
    	h.Insert(Int(8))
    	h.Insert(Int(7))
    	h.Insert(Int(6))
    	h.Insert(Int(3))
    	h.Insert(Int(1))
    	h.Insert(Int(0))
    	h.Insert(Int(2))
    	h.Insert(Int(4))
    	h.Insert(Int(9))
    	h.Insert(Int(5))
    
    	sorted := make([]Int, 0)
    	for h.Len() > 0 {
        
    		sorted = append(sorted, h.Delete().(Int))
    	}
    
    	for i := 0; i < len(sorted)-2; i++ {
        
    		if sorted[i] < sorted[i+1] {
        
    			fmt.Println(sorted)
    			t.Error()
    		}
    	}
    }

#### 优先队列实现 ####

package main
    
    import (
    	"fmt"
    )
    
    type PQItem struct {
        
    	Value interface{
        }
    	Priority  int
    }
    
    func (p PQItem) Less(than HeapItem) bool {
        
    	return p.Priority < than.(PQItem).Priority
    }
    
    func NewPQItem(v interface{
        }, priority int) *PQItem  {
        
    	return &PQItem{
        
    		Value:    v,
    		Priority: priority,
    	}
    }
    
    type PQ struct {
        
    	data  Heap
    }
    
    func NewMaxPQ() *PQ {
        
    	return &PQ{
        
    		data:*NewHeapMax(),
    	}
    }
    
    func NewMinPQ() *PQ  {
        
    	return &PQ{
        
    		data:*NewHeapMin(),
    	}
    }
    
    func (pq *PQ)Empty() bool  {
        
    	return pq.data.Empty()
    }
    
    func (pq *PQ)Len() int  {
        
    	return pq.data.Len()
    }
    
    // data是[]heapItem的，因此只要PQ实现了heapItem的接口就可以
    func (pq *PQ)Insert(v PQItem)  {
        
    	pq.data.Insert(v)
    }
    
    func (pq *PQ)Delete()( PQItem){
        
    	return pq.data.Delete().(PQItem)
    }
    
    func (pq *PQ)ChangePriority(val interface{
        }, priority int) (err error) {
        
    	// 先判断当前队列中有没有val。
    	var storeage []PQItem
    
    
    	found := pq.Delete()
    	for found.Value != val {
        
    		if pq.Len() == 0 {
        
    			err =  fmt.Errorf("Item not found")
    			break
    		}
    		storeage = append(storeage, found)
    		found = pq.Delete()
    	}
    
    	// 跳出循环： err == nil --->   found.Value == value
    	 //           err != nil  ---> found.Value != value
    
    	// 找到了
    	if err == nil {
        
    		found.Priority = priority
    	}
    
    	pq.data.Insert(found)
    
    	for len(storeage) > 0  {
        
    		var el PQItem
    		el, storeage = storeage[0], storeage[1:]
    		pq.data.Insert(el)
    	}
    
    	return nil
    }

测试：

package main
    
    import (
    	"fmt"
    	"testing"
    )
    
    func TestMaxPriorityQueue(t *testing.T) {
        
    	h := NewMaxPQ()
    
    	h.Insert(*NewPQItem(8, 10))
    	h.Insert(*NewPQItem(7, 11))
    	h.Insert(*NewPQItem(6, 12))
    	h.Insert(*NewPQItem(3, 13))
    	h.Insert(*NewPQItem(1, 14))
    	h.Insert(*NewPQItem(0, 15))
    	h.Insert(*NewPQItem(2, 16))
    	h.Insert(*NewPQItem(4, 17))
    	h.Insert(*NewPQItem(9, 18))
    	h.Insert(*NewPQItem(5, 19))
    
    	sorted := make([]PQItem, 0)
    	for h.Len() > 0 {
        
    		sorted = append(sorted, h.Delete())
    	}
    
    	for i := 0; i < len(sorted)-2; i++ {
        
    		if sorted[i].Priority < sorted[i+1].Priority {
        
    			fmt.Println(sorted)
    			t.Error()
    		}
    	}
    }
    
    
    func TestMinPriorityQueue(t *testing.T) {
        
    	h := NewMinPQ()
    
    	h.Insert(*NewPQItem(8, 10))
    	h.Insert(*NewPQItem(7, 11))
    	h.Insert(*NewPQItem(6, 12))
    	h.Insert(*NewPQItem(3, 13))
    	h.Insert(*NewPQItem(1, 14))
    	h.Insert(*NewPQItem(0, 15))
    	h.Insert(*NewPQItem(2, 16))
    	h.Insert(*NewPQItem(4, 17))
    	h.Insert(*NewPQItem(9, 18))
    	h.Insert(*NewPQItem(5, 19))
    
    	sorted := make([]PQItem, 0)
    	for h.Len() > 0 {
        
    		sorted = append(sorted, h.Delete())
    	}
    
    	for i := 0; i < len(sorted)-2; i++ {
        
    		if sorted[i].Priority > sorted[i+1].Priority {
        
    			fmt.Println(sorted)
    			t.Error()
    		}
    	}
    }
    
    func TestChangePriority(t *testing.T) {
        
    	h := NewMaxPQ()
    
    	h.Insert(*NewPQItem(8, 10))
    	h.Insert(*NewPQItem(7, 11))
    	h.Insert(*NewPQItem(6, 12))
    	h.Insert(*NewPQItem(3, 13))
    	h.Insert(*NewPQItem(1, 14))
    	h.Insert(*NewPQItem(0, 15))
    	h.Insert(*NewPQItem(2, 16))
    	h.Insert(*NewPQItem(4, 17))
    	h.Insert(*NewPQItem(9, 18))
    	h.Insert(*NewPQItem(5, 19))
    
    	h.ChangePriority(8, 66)
    	popped := h.Delete()
    
    	if popped.Value != 8 {
        
    		t.Error()
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/a473fa39c02e4d8fbb742755af531b46.png
[https_github.com_gammazero_deque]: https://github.com/gammazero/deque
[Link 1]: https://www.jianshu.com/p/79cfba94cb0f
[Link 2]: https://blog.csdn.net/zhizhengguan/article/details/106826270
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230209/521d2631156a4897a989ac582ff57fc5.png