go语言数据结构 环形队列
1.环形队列是什么
队列是一种常用的数据结构，这种结构保证了数据是按照“先进先出”的原则进行操作的，即最先进去的元素也是最先出来的元素.环形队列是一种特殊的队列结构，保证了元素也是先进先出的，但与一般队列的区别是，他们是环形的，即队列头部的上个元素是队列尾部，通常是容纳元素数固定的一个闭环。
C代码实现见:https://github.com/dodng/fast_ring_queue
2.环形队列的优点
1.保证元素是先进先出的
是由队列的性质保证的，在环形队列中通过对队列的顺序访问保证。
2.元素空间可以重复利用
因为一般的环形队列都是一个元素数固定的一个闭环，可以在环形队列初始化的时候分配好确定的内存空间，当进队或出队时只需要返回指定元素内存空间的地址即可，这些内存空间可以重复利用，避免频繁内存分配和释放的开销。
3.为多线程数据通信提供了一种高效的机制。
在最典型的生产者消费者模型中，如果引入环形队列，那么生成者只需要生成“东西”然后放到环形队列中即可，而消费者只需要从环形队列里取“东西”并且消费即可，没有任何锁或者等待，巧妙的高效实现了多线程数据通信。
3.环形队列的工作场景
一般应用于需要高效且频繁进行多线程通信传递数据的场景，例如：linux捕包、发包等等，（linux系统中对PACKET_RX_RING和PACKET_TX_RING的支持实质就是内核实现的一种环形队列）
实际环形队列在工作时有3种情况：
3.1 入队速度=出队速度
这是环形队列的常态，即入队速度和出队速度大致一样，即使某个突然时刻入队速度陡然变高或者出队速度陡然变低，都能通过队列这个缓冲区把这些数据先存起来，等到能处理的时候再处理。
3.2 入队速度>出队速度
在这种情况下，队列“写入”的速度>“读取”的速度，想象当这种状态持续一段时间之后，队列中大多数全是写入但没读取的元素，当又一个新的元素产生时，可以把这个新元素drop掉或者放在另一个缓冲区保存起来，这种情况的出现不是个好事情，说明你需要对出队处理元素的算法或逻辑优化处理速度了。
3.3 入队速度<出队速度
在这种情况下，队列“读取”速度>“写入”速度，这种情况说明程序出队处理元素的速度很快，这是比较好的情况，唯一不足的是读取队列的时候可能经常会轮询队列是否有新的元素，造成cpu占用过高。
4.无锁环形队列的实现
4.1环形队列的存储结构
链表和线性表都是可以的，但几乎都用线性表实现，比链表快很多，原因也是显而易见的，因为访问链表需要挨个遍历。
4.2读写index
有2个index很重要，一个是写入index，标示了当前可以写入元素的index，入队时使用。一个是读取index，标示了当前可以读取元素的index，出队时使用。
4.3元素状态切换
有种很巧妙的方法，就是在队列中每个元素的头部加一个元素标示字段，标示这个元素是可读还是可写，而这个的关键就在于何时设置元素的可读可写状态，参照linux内核实现原理，当这个元素读取完之后，要设置可写状态，当这个元素写入完成之后，要设置可读状态。
5.实际测试效果
在CentOS 5.5 (cpu每核主频1200MHz)设备上简单测试了一下。环形队列大小为10000，元素数据大小为4字节，每秒可以写入并读取的元素是250万左右，即250pps.
C代码实现见:https://github.com/dodng/fast_ring_queue
Go实现
queen.go
package data_struct
import "log"
//环形队列实现 队列，先进先出。追加至队尾，弹出队顶
type Queen struct {
Length int64 //队列长度
Capacity int64 //队列容量
Head int64 //队头
Tail int64 //队尾 D
ata []interface{}
}
//初始化
func MakeQueen(length int64) Queen {
var q = Queen{
Length: length,
Data: make([]interface{}, length),
}
return q
}
//判断是否为空
func (t *Queen) IsEmpty() bool {
return t.Capacity == 0
}
//判断是否满
func (t *Queen) IsFull() bool {
return t.Capacity == t.Length
}
//加一个元素
func (t *Queen) Append(element interface{}) bool {
if t.IsFull() {
log.Println("队列已满 ，无法加入")
return false
}
t.Data[t.Tail] = element
t.Tail++
t.Capacity++
return true
}
//弹出一个元素，并返回
func (t *Queen) OutElement() interface{} {
if t.IsEmpty() {
log.Println("队列为空，无法弹出")
}
defer func() {
t.Capacity-- t.Head++
}()
return t.Data[t.Head]
}
//遍历
func (t *Queen) Each(fn func(node interface{})) {
for i := t.Head; i < t.Head+t.Capacity; i++ {
fn(t.Data[i%t.Length])
}
}
//清空
func (t *Queen) Clcear() bool {
t.Capacity = 0
t.Head = 0
t.Tail = 0
t.Data = make([]interface{},
t.Length)
return true
}queen_test.go
package data_struct
import (
"fmt"
"testing"
)
func TestQueen(t *testing.T) {
var testLength = int64(4)
q := MakeQueen(testLength)
if q.Length != testLength {
t.Error("MakeQueen(4)的容量不是4")
}
q.Append(10)
q.Append(12)
q.Append(14)
q.Append(16)
//q.Append(18)
q.OutElement()
//fmt.Println(q.OutElement())
if q.Capacity != 3 {
t.Error("队队长度不正确")
}
q.Each(func(node interface{}) {
fmt.Println(node) })
q.Clcear()
if q.Capacity != 0 {
t.Error("queen的长度不为0")
}
q.Each(func(node interface{}) {
fmt.Println(node)
})
q.Append("B")
q.Append('A')
q.Each(func(node interface{}) {
fmt.Println(node)
})
}版权申明：内容来源网络，版权归原创者所有。除非无法确认，我们都会标明作者及出处，如有侵权烦请告知，我们会立即删除并表示歉意。谢谢。
腾讯云开发者
