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) 
}) 
}

版权申明:内容来源网络,版权归原创者所有。除非无法确认,我们都会标明作者及出处,如有侵权烦请告知,我们会立即删除并表示歉意。谢谢。

本文分享自微信公众号 - Golang语言社区(Golangweb)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-05-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏FreeBuf

使用Burpsuite扩展Hackvertor绕过WAF并解密XOR

最近,我一直在忙于开发自己的一个Burp扩展Hackvertor。这是一个具有基于标签转换功能的编码器,相比起Burp内置的解码器它的功能要强大的多。通过标签的...

16410
来自专栏用户2442861的专栏

STL map, hash_map , unordered_map区别、对比

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

66550
来自专栏一个会写诗的程序员的博客

一致性(连续性)hash算法(Consistent hashing)一致性(连续性)hash算法(Consistent hashing)

Consistent hashing is a scheme that provides hash table functionality in a way t...

16020
来自专栏菩提树下的杨过

DateTime在ExtJs中无法正确序列化的问题

这几天在学习ExtJs + Wcf的过程中,发现一个问题,如果Class中有成员的类型为DateTime,即使我们正常标识了[DataMember],序列化成J...

218100
来自专栏全沾开发(huā)

使用box-shadow进行画图(性能优化终结者)

19620
来自专栏对角另一面

lodash源码分析之自减的两种形式

本文为读 lodash 源码的第六篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

221100
来自专栏CSDN技术头条

使用Go语言来理解Tensorflow

【译者注】本文通过一个简单的Go绑定实例,让读者一步一步地学习到Tensorflow有关ID、作用域、类型等方面的知识。以下是译文。 Tensorflow并不是...

297100
来自专栏数据分析

[数据分析工具] Pandas 不可不知的功能(一)

如果你在使用 Pandas(Python Data Analysis Library) 的话,下面介绍的对你一定会有帮助的。 首先我们先介绍一些简单的概念 D...

42760
来自专栏人工智能头条

TensorFlow架构与设计:OP本质论

26840
来自专栏软件开发 -- 分享 互助 成长

分解成3NF的保持函数依赖的分解算法:

转换成3NF的保持函数依赖的分解算法: ρ={R1<U1,F1>,R2<U2,F2>,...,Rk<Uk,Fk>}是关系模式R<U,F>的一个分解,U={A1,...

40750

扫码关注云+社区

领取腾讯云代金券