循环队列、以及环形缓冲区
06 Oct 2021循环队列
普通队列的入队操作将队尾指针后移+1，出队操作将队头指针后移+1，操作几次之后会发现队头指针和队尾指针都跑到缓冲区的尾部去了，这就导致了前面的内存空间全被浪费，如果要重新恢复使用，则需要进行元素和指针的移动
显然这种队列使用方式太不方便了，所以就诞生了环形队列「不用搬移元素和指针，一直可以重复利用这段内存空间」。
golang 的有缓冲的 channel 通道，内部就包含了一个环形队列
如何判断环形队列为空，为满，有两种方式:
一. 是附加一个标志位 isFull
- 当 head 赶上 tail，队列空，则令 isFull=0,
- 当tail 赶上 head，队列满，则令 isFull=1,
二. 限制 tail 赶上 head，即队尾结点与队首结点之间至少留有一个元素的空间。
- 队列空： head == tail
- 队列满： (tail+1)% MAXN == head
代码示例：
ppackage queue
import (
"errors"
"fmt"
)
type Queue struct {
data []interface{}
head int // 队首
tail int // 队尾
size int // 队列长度
}
// NewQueue 新建指定长度的队列
func NewQueue(size int) *Queue {
return &Queue{make([]interface{}, size+1), 0, 0, 0}
}
// CapaCity 获取容量
// 限制 tail 追上 head，即队尾结点与队首结点之间至少留有一个元素的空间。
func (q *Queue) CapaCity() int {
return len(q.data) - 1
}
func (q *Queue) IsEmpty() bool {
return q.head == q.tail
}
func (q *Queue) Len() int {
return q.size
}
// Enqueue 入队
func (q *Queue) Enqueue(x interface{}) {
q.grow(q.CapaCity() * 2)
q.data[q.tail] = x
q.tail = (q.tail + 1) % len(q.data)
q.size++
}
// grow 队列扩容
func (q *Queue) grow(new_capacity int) {
// 队列已满，需要扩容
if q.head == (q.tail+1)%len(q.data) {
new_data := make([]interface{}, new_capacity+1)
for i := 0; i < q.Len(); i++ {
new_data[i] = q.data[(i+q.head)%len(q.data)]
}
q.data = new_data
q.head, q.tail = 0, q.size
fmt.Println("queue resized to ", q.size)
}
}
// Dequeue 出队
func (q *Queue) Dequeue() (interface{}, error) {
if q.IsEmpty() {
return nil, errors.New("Cannot dequeue from an empty queue.")
}
x := q.data[q.head]
q.data[q.head] = nil
q.head = (q.head + 1) % q.CapaCity()
q.size--
if q.size == q.CapaCity()/4 && q.CapaCity()/2 != 0 {
q.grow(q.CapaCity() / 2)
}
return x, nil
}
// Gethead， 获取队首元素
func (q *Queue) Gethead() (interface{}, error) {
if q.IsEmpty() {
return nil, errors.New("Queue is empty.")
}
return q.data[q.head], nil
}
func (q *Queue) String() string {
return fmt.Sprintf("cap: %d size: %d data: %v head: %d tail: %d", q.CapaCity(), q.Len(), q.data, q.head, q.tail)
}
环形缓冲器
环形缓冲器（ringr buffer），也称作圆形队列（circular queue），循环缓冲区（cyclic buffer），圆形缓冲区（circula buffer），是一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构，适合缓存数据流。 和循环队列类似的实现，区别在于存储字节类型数据
对于 I/O 较重的应用程序，可以使用环形缓冲替换 bytes.Buffer，因为开启了固定的一块连续内存，可节省减少内存消耗
看下图是个非常有意思的东西：
开源的线程安全的环形缓冲实现在： https://github.com/smallnest/ringbuffer
看上去已经很完善了，这里就不重复实现了