Ring buffer

环形缓冲区也称为循环缓冲区。

基于数组的队列的问题是在队列后面添加新项目很快，O（1），但是从队列前面删除项目很慢，O（n）。删除速度很慢，因为它需要在内存中移动剩余的数组元素。

实现队列的更有效方法是使用环形缓冲区或循环缓冲区。这是一个概念性地回绕到开头的数组，因此您永远不必删除任何项目。所有操作都是O（1）。

原则上它是如何工作的。我们有一个固定大小的数组，比如5项：

image.png

最初，数组为空，read（r）和write（w）指针位于开头。

让我们为这个数组添加一些数据。添加字母"A"

image.png

每次添加数据时，写指针都向前移动一步。让我们添加一些元素BCD：

image.png

现在阵列中还有一个空间，现在读取一些数据，而不是将另一个元素加入队列。因为写指针位于读指针之前，这意味着数据可用于读取。读取指针随着读取可用数据而前进：

image.png

让我们再读两个BC：

image.png

现在，应用程序决定再次写入两个数据项，E并且F：

image.png

哎呀，写指针已到达数组的末尾，因此没有更多的空间来容纳对象F。现在怎么办？好吧，这就是为什么它是循环缓冲区：我们将写指针包装回到开头并写入剩余数据：

image.png

现在，我们可以读其余三个项目D, E和F。

image.png

当然，当读指针到达缓冲区的末尾时，它也会回绕：

image.png

现在缓冲区再次为空，因为读指针已经赶上了写指针。

public struct RingBuffer<T> {
    
    /// 声明一个数组, 用来存储数据, 因为循环缓冲的数据里面存在空值, 所以类型为T?
    private var array: [T?] = []
    /// 记录读取的索引
    private var readIndex = 0
    /// 记录写入的索引
    private var writeIndex = 0
    
    /// 初始化方法, 需要指定循环缓冲区的大小
    public init(count: Int) {
        array = Array<T?>(repeating: nil, count: count)
    }
    
    /// 循环缓冲区的第一个值, 返回值为可选值
    public var first: T? {
        return array[readIndex]
    }
    
    /// 写数据, 这里需要判断缓冲区是否已满, 如果已满, 则不进行写入操作, 返回false, 否则, 继续写入
    /**
     * 现在我们采用的是不会覆盖原有数据的模式, 当缓冲区满了, 不能继续写入了, 要开始读, 每读一个, 就会空出一个可以写入的空间, read和writer方法中,
     * readIndex 和 writeIndex 总是递增的, 无论是一直读或者是一直写, 索引总会超出数组的长度.
     * 这里使用取模运算, 因为缓冲区的长度是固定的, 随着index的递增, 索引值总是从0到count - 1循环
     */
    @discardableResult
    public mutating func write(_ element: T) -> Bool {
        // 首先判断缓冲区是否满了, 如果
        if isFull == false {
            print("\(element) = \(writeIndex % array.count)")
            array[writeIndex % array.count] = element
            writeIndex += 1
            return true
        } else {
            return false
        }
    }
    
    @discardableResult
    public mutating func read() -> T? {
        if isEmpty == false {
            let element = array[readIndex % array.count]
            readIndex += 1
            return element
        } else {
            return nil
        }
    }
    
    /// 判断是否有可读的数据, 如果读和写的索引值一样, 说明, 已经读完了
    private var availableSpaceForReading: Int {
        return writeIndex - readIndex
    }
    
    ///
    public var isEmpty: Bool {
        return availableSpaceForReading == 0
    }
    
    /// 是否可写, 空间的总长度 - (读索引和写索引之间的间距)
    private var availableSpaceForWriting: Int {
        return array.count - availableSpaceForReading
    }
    
    public var isFull: Bool {
        return availableSpaceForWriting == 0
    }
}

var buffer = RingBuffer<String>(count: 5)
        
        buffer.write("A")
        buffer.write("B")
        buffer.write("C")
        buffer.write("D")
        
        
        buffer.read()   // A
        buffer.read()   // B
        buffer.read()   // C
        
        buffer.write("E")
        buffer.write("F")
        buffer.read()   // D
        buffer.read()   // E
        buffer.read()   // F
        buffer.read()   // nil

这里实现的循环缓冲和理论上的有些差距, 理论上来说, 循环缓冲区如果已满, 并且执行后续写入时，它将开始覆盖最旧的数据.
当缓冲区已满, 是继续写入覆盖最久的数据, 还是抛出异常, 禁止覆盖最旧的数据, 这完全取决于当前应用程序的使用场景
比如, 使用循环缓冲区来实现队列, 当缓冲区已满不应该继续写入, 否则队列的数据就会丢失

您已经看到环形缓冲区可以创建更优的队列，但它也有一个缺点：调整队列大小变得低效。但如果是一个固定大小的队列，那么循环缓冲将很适用。