环形队列

环形队列的优点

1. 保证元素是先进先出的。是由队列的性质保证的，在环形队列中通过对队列的顺序访问保证。

2. 元素空间可以重复利用。因为一般的环形队列都是一个元素数固定的一个闭环，可以在环形队列初始化的时候分配好确定的内存空间，当进队或出队时只需要返回指定元素内存空间的地址即可，这些内存空间可以重复利用，避免频繁内存分配和释放的开销。

3. 为多线程数据通信提供了一种高效的机制。在最典型的生产者消费者模型中，如果引入环形队列，那么生成者只需要生成“东西”然后放到环形队列中即可，而消费者只需要从环形队列里取“东西”并且消费即可，没有任何锁或者等待，巧妙的高效实现了多线程数据通信。

接口

package ring_queue

type RingQueueInterface interface {
    // 获取队列中元素个数
    Len() int
    // 获取队首元素
    Head() interface{}
    // 获取队尾元素
    Tail() interface{}
    // 从队尾添加元素
    Insert(x interface{}) bool
    // 移除队首元素
    LPop() bool
    // 队列已满
    IsFull() bool
    // 队列为空
    Empty() bool
}

type RingDequeInterface interface {
    // 移除队尾元素
    Pop() bool
    // 从队首添加元素
    LInsert(x interface{}) bool
    RingQueueInterface
}

环形队列（阻塞版，环形缓冲器）实现

当队列元素满时，不能继续插入元素。 无锁版也支持多线程，已验证数据安全性，也就是没有必要使用加读写锁的环形队列

阻塞版环形队列 PK channel

阻塞版环形队列较优

ringQueueBlock_Insert, 708, 771, 623, 743, 652, 665, 501, 560, 555, 529, 543, 471, 477, 528, 487, 505, 486, 544, 483, 476,
ringQueueBlock_LPop, 533, 584, 594, 507, 583, 563, 515, 512, 486, 607, 696, 534, 487, 539, 468, 475, 484, 482, 510, 501,
channel_Insert, 864, 644, 897, 1020, 707, 907, 484, 561, 576, 621, 921, 591, 534, 498, 463, 552, 487, 468, 473, 544,
channel_LPop, 698, 624, 736, 722, 838, 763, 750, 696, 625, 745, 700, 675, 668, 909, 825, 699, 691, 802, 882, 760,

有锁版环形队列 PK 无锁版环形队列

ringQueueBlock_Insert, 1115, 686, 662, 650, 626, 628, 647, 632, 614, 649, 609, 577, 548, 521, 553, 518, 511, 505, 545, 531, 
ringQueueBlock_LPop, 542, 517, 562, 525, 492, 550, 523, 563, 518, 541, 538, 505, 520, 545, 534, 522, 598, 538, 533, 553, 
ringQueueBlockRWLock_Insert, 1324, 1041, 1073, 1105, 1072, 896, 527, 547, 565, 562, 678, 614, 607, 557, 575, 552, 586, 570, 539, 597, 
ringQueueBlockRWLock_LPop, 881, 1067, 925, 936, 994, 875, 579, 578, 503, 751, 515, 524, 551, 589, 615, 583, 567, 586, 594, 541,

无锁版环形队列对并发的支持（验证性实验）

// 理论上最后队列中有1000个元素
// 有锁版有1002个
// 无锁版有960个

var wg sync.WaitGroup

// 有锁版环形队列对并发的支持
func case5() {
    var cnt = 1000
    var rq = ring_queue.NewRingQueueBlockRWLock(5 * cnt)
    for i := 0; i < cnt*4; i++ {
        var v = i
        wg.Add(1)
        if i % 4 == 0 {
            go func() {
                rq.LPop()
                wg.Done()
            }()
        } else if i % 4 == 1{
            go func() {
                rq.Head()
                wg.Done()
            }()
        } else {
            go func() {
                rq.LInsert(v)
                wg.Done()
            }()
        }
    }
    wg.Wait()
    fmt.Println(rq.Len())  // 1002
    for !rq.Empty() {
        fmt.Println(rq.Head())
        rq.LPop()
    }
}

// 无锁版环形队列对并发的支持
func case4() {
    var cnt = 1000
    var rq = ring_queue.NewRingQueueBlock(5 * cnt)
    for i := 0; i < cnt*4; i++ {
        var v = i
        wg.Add(1)
        if i % 4 == 0 {
            go func() {
                rq.LPop()
                wg.Done()
            }()
        } else if i % 4 == 1{
            go func() {
                rq.Head()
                wg.Done()
            }()
        } else {
            go func() {
                rq.LInsert(v)
                wg.Done()
            }()
        }
    }
    wg.Wait()
    fmt.Println(rq.Len())    // 960
    for !rq.Empty() {
        fmt.Println(rq.Head())
        rq.LPop()
    }
}

环形队列（阻塞版）小结

建议使用无锁版环形队列，它支持并发操作

环形队列（非阻塞版）实现 TODO: 待实现以及数据验证

github.com/1005281342/basic_component/ring_queue_nonblocking

需要考虑在队列中没有元素时执行pop（弹出）动作，在本实现中不会提示队列为空切返回的元素为nil。

注意在本实现中如果队列满了继续插入元素则会覆盖队尾元素（队尾元素会被弹出）。

参考

https://github.com/el10savio/goCircularRingBuffer/blob/master/ringbuffer/ringbuffer.go

https://github.com/cxt90730/safe-queue/blob/master/Queue.go（可以利用读写锁对其进行优化）