简介

队列在在各种各样的程序中广泛运用，队列虽然是比较简单的数据结构，但是非常灵活，有各种各样的实现，根据存储数据的底层结构不同可以分为数组和链表实现，根据功能可以分为先进先出（FIFO）队列、双端队列、循环队列等。这里重点讨论一下循环队列（循环缓存区）的应用场景及实现。

循环队列是有一块固定大小的内存，在逻辑上成环，向队列中加入数据或向队列中获取数据时，不需要像数组一样对元素进行移动，循环队列有两个指针，头指针和尾指针，向队列中添加数据时，头指针向前移动，获取数据时，尾指针向前移动，如果指针到了整个队列的末尾则重新指向队列的起始位置。

应用场景

  • 对于固定大小的循环队列来说，因为不需要动态分配内存，可以直接放到数据段，这样非常适合应用在嵌入式系统。
  • 在生产者和消费者速率有差别时充当缓冲区，当消费者的速率无法跟上生产者的速率时，老的数据会被覆盖，循环缓存区保证总是消费最新的数据。这种在网络 IO 程序中有非常广泛的应用，linux 网卡驱动程序中对网络包的接收发送缓存区就是循环队列（ring buffer）实现的。Go的有buffer的channel也是基于这种循环队列实现的。

实现

循环队列的实现一个比较关键的问题是如何判断队列已经满了，这里一般有两种方式：

  • 浪费一个位置不存储数据，用来判断队列是不是满的，当队列是是满的时 head + 1 == tail，空时：head == tail。
  • 使用一个标志变量 full 来表示队列是不是满的，当队列是是满的时 full == true，空时：head == tail && !full。

下面是使用标志变量来实现循环队列的Golang代码：

基本结构

1
2
3
4
5
6
7
8
9

// Circular Buffer ensures that we are always consuming the most recent data
type CircularBuffer struct {
	buffer   []interface{}
	head     int
	tail     int
	capacity int
	full     bool
	mu       sync.RWMutex
}

初始化和重置

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// New circular Buffer with fixed size
func New(capacity int) *CircularBuffer {
	return &CircularBuffer{
		buffer:   make([]interface{}, capacity),
		capacity: capacity,
	}
}

// Reset circular Buffer
func (c *CircularBuffer) Reset() {
	c.mu.Lock()
	defer c.mu.Unlock()
	c.head = c.tail
	c.full = false
}

返回队列状态

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

// Reset circular Buffer
func (c *CircularBuffer) Reset() {
	c.mu.Lock()
	defer c.mu.Unlock()
	c.head = c.tail
	c.full = false
}

// Empty returns true if the buffer is empty
func (c *CircularBuffer) Empty() bool {
	c.mu.RLock()
	defer c.mu.RUnlock()
	return !c.full && (c.head == c.tail)
}

// Full returns true if the buffer is full
func (c *CircularBuffer) Full() bool {
	c.mu.RLock()
	defer c.mu.RUnlock()
	return c.full
}

// Capacity returns the capacity of buffer
func (c *CircularBuffer) Capacity() int {
	c.mu.RLock()
	defer c.mu.RUnlock()
	return c.capacity
}

// Size returns the size of buffer
func (c *CircularBuffer) Size() int {
	c.mu.RLock()
	defer c.mu.RUnlock()
	size := c.capacity
	if !c.full {
		if c.head >= c.tail {
			size = c.head - c.tail
		} else {
			size = c.capacity + c.head - c.tail
		}
	}
	return size
}

插入获取元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// Put item to buffer
func (c *CircularBuffer) Put(item interface{}) {
	c.mu.Lock()
	defer c.mu.Unlock()
	c.buffer[c.head] = item
	if c.full {
		c.tail = (c.tail + 1) % c.capacity
	}
	c.head = (c.head + 1) % c.capacity
	c.full = c.head == c.tail
}

// Get item from buffer
func (c *CircularBuffer) Get() interface{} {
	c.mu.Lock()
	defer c.mu.Unlock()
	if !c.full && (c.head == c.tail) {
		return nil
	}
	item := c.buffer[c.tail]
	c.full = false
	c.tail = (c.tail + 1) % c.capacity
	return item
}

总结

循环队列虽然是比较简单的数据结构却在各种各样的程序中发挥着重要作用，写的程序多了慢慢明白了一个好的系统不是他用了多么花哨多么前沿的技术而是他正确的运用了数据结构。Linus Torvals 说：“烂程序员关心的是代码。好程序员关心的是数据结构和它们之间的关系。” Rob 的五个编程原则之一：“数据占主导地位（Data dominates）。如果你选择了正确的数据结构，并且已把事情组织好，那么算法的效率显而易见。编程的核心是数据结构，不是算法。” 大佬的话不一定全对但是肯定是根据他们的编程经验总结出来的，最近也有类似的感悟，特别是感觉到数据如何存十分重要，选择适合的数据结构来存储数据，拆分数据，可以灵活地应对各种需求，但是如果数据存储混乱，那么获取数据困难，计算数据困难，即使再多的数据，再好的算法也无法发挥数据的价值。对于自己来说还是得好好地熟悉这些简单基础的数据结构。