做了什么

这是源码Queue.swift文件开头的一段描述

Data structure that represents queue.
Complexity of enqueue, dequeue is O(1) when number of operations is averaged over N operations.
Complexity of peek is O(1).

一般实现（数组实现）

//MARK: - 队列的基本实现
public struct Queue<T> {
    
    // 泛型数组：用于存储数据元素
    fileprivate var data = [T]()
    
    /// 构造函数：创建一个空的队列
    public init() {}

    /// 入队列操作：将元素添加到队列的末尾
    /// -复杂度: O(1)
    /// -参数element: 一个类型为T的元素
    public mutating func enqueue(_ element: T) {
        data.append(element)
    }
    
    /// 出队列操作：删除并返回队列中的第一个元素
    /// -returns:
    /// -如果队列不为空，则返回第一个类型为T的元素
    /// -如果队列为空，则返回nil
    public mutating func dequeue() -> T? {
        return data.removeFirst()
    }
    
    /// 返回队列中的第一个元素(不删除)
    /// -returns:
    /// -如果队列不为空，则返回第一个类型为T的元素
    /// -如果队列为空，则返回nil
    public func peek() -> T? {
        return data.first
    }
    
    /// 将队列重置为空状态
    public mutating func clear() {
        data.removeAll()
    }
    
    /// 返回队列中元素的个数
    public var count: Int {
        return data.count
    }
    
    /// 计算属性：返回队列的存储容量
    /// - get：获取队列的存储空间，但不会分配新的存储空间
    /// - set：分配足够的空间来存储指定数量的元素
    public var capacity: Int {
        get {
            return data.capacity
        }
        set {
            data.reserveCapacity(newValue)
        }
    }
    
    /// 检查队列是否已满
    /// -returns: 如果队列已满，则返回true，否则返回false
    public func isFull() -> Bool {
        return count == data.capacity
    }
    
    /// 检查队列是否为空
    /// - returns: 如果队列为空，则返回true，否则返回false
    public func isEmpty() -> Bool {
        return data.isEmpty
    }
}

咋一看，我们的队列的实现没什么问题。但RxSwift的作者是这么做的么？首先我们来探究下我们的实现中enqueue、dequeue的Complexity。

探究算法复杂度

enqueue算法复杂度分析

enqueue：一般情况下：Complexity为O(1)、需要扩容时为O(n)

因为Array的appen的Complexity就是这个情况

Swift扩容原理

来自接口

/// Because arrays increase their allocated capacity using an exponential
    /// strategy, appending a single element to an array is an O(1) operation
    /// when averaged over many calls to the `append(_:)` method. When an array
    /// has additional capacity and is not sharing its storage with another
    /// instance, appending an element is O(1). When an array needs to
    /// reallocate storage before appending or its storage is shared with
    /// another copy, appending is O(*n*), where *n* is the length of the array.
    ///
    /// - Parameter newElement: The element to append to the array.
    ///
    /// - Complexity: O(1) on average, over many calls to `append(_:)` on the
    ///   same array.
    @inlinable public mutating func append(_ newElement: __owned Element)

dequeue算法复杂度分析

dequeue: Complexity为O(n)

因为Array的removeFirst的Complexity为O(n)

    /// 来自文档
 /// - Returns: The removed element.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the collection.
    @inlinable public mutating func removeFirst() -> Element

为什么Complexity为O(n)呢？我们去看下源码。
我找到源码的步骤。

• 写了个demo,并添加了removeFirst的符号断点。如下图：

  
  
  image
• 选择Xcode -> Debug -> Debug Workflow -> Always show Disassembly: 显示汇编

• 运行、进入断点。可看到如下图所示.

  
  
  image
• 于是到苹果的源码中搜索removeFirst()。但是搜到两个，分别如下

extension RangeReplaceableCollection where SubSequence == Self {
  /// Removes and returns the first element of the collection.
  ///
  /// The collection must not be empty.
  ///
  /// Calling this method may invalidate all saved indices of this
  /// collection. Do not rely on a previously stored index value after
  /// altering a collection with any operation that can change its length.
  ///
  /// - Returns: The first element of the collection.
  ///
  /// - Complexity: O(1)
  @inlinable
  @discardableResult
  public mutating func removeFirst() -> Element {
    _precondition(!isEmpty, "Can't remove items from an empty collection")
    let element = first!
    self = self[index(after: startIndex)..<endIndex]
    return element
  }

 /// Removes and returns the first element of the collection.
  ///
  /// The collection must not be empty.
  ///
  ///     var bugs = ["Aphid", "Bumblebee", "Cicada", "Damselfly", "Earwig"]
  ///     bugs.removeFirst()
  ///     print(bugs)
  ///     // Prints "["Bumblebee", "Cicada", "Damselfly", "Earwig"]"
  ///
  /// Calling this method may invalidate any existing indices for use with this
  /// collection.
  ///
  /// - Returns: The removed element.
  ///
  /// - Complexity: O(*n*), where *n* is the length of the collection.
  @inlinable
  @discardableResult
  public mutating func removeFirst() -> Element {
    _precondition(!isEmpty,
      "Can't remove first element from an empty collection")
    let firstElement = first!
    removeFirst(1)
    return firstElement
  }

一个Complexity为O(1),另一个Complexity为 O(n)。此时其实我们可以根据之前看到的文档,应该能猜到第二个才是正真的源码实现。所以我们暂且不管Complexity为O(1)的实现了。而另外一个实现又调用了removeFirst(1)。其实现如下：

/// Removes the specified number of elements from the beginning of the
  /// collection.
  ///
  ///     var bugs = ["Aphid", "Bumblebee", "Cicada", "Damselfly", "Earwig"]
  ///     bugs.removeFirst(3)
  ///     print(bugs)
  ///     // Prints "["Damselfly", "Earwig"]"
  ///
  /// Calling this method may invalidate any existing indices for use with this
  /// collection.
  ///
  /// - Parameter k: The number of elements to remove from the collection.
  ///   `k` must be greater than or equal to zero and must not exceed the
  ///   number of elements in the collection.
  ///
  /// - Complexity: O(*n*), where *n* is the length of the collection.
  @inlinable
  public mutating func removeFirst(_ k: Int) {
    if k == 0 { return }
    _precondition(k >= 0, "Number of elements to remove should be non-negative")
    _precondition(count >= k,
      "Can't remove more items from a collection than it has")
    let end = index(startIndex, offsetBy: k)
    removeSubrange(startIndex..<end)
  }

内部又调用了removeSubrange(startIndex..<end)，实现如下,有两个版本，分别如下：

@inlinable
  public mutating func removeSubrange(_ bounds: Range<Index>) {
    replaceSubrange(bounds, with: EmptyCollection())
  }

/// Removes the elements in the specified subrange from the collection.
  ///
  /// All the elements following the specified position are moved to close the
  /// gap. This example removes three elements from the middle of an array of
  /// measurements.
  ///
  ///     var measurements = [1.2, 1.5, 2.9, 1.2, 1.5]
  ///     measurements.removeSubrange(1..<4)
  ///     print(measurements)
  ///     // Prints "[1.2, 1.5]"
  ///
  /// Calling this method may invalidate any existing indices for use with this
  /// collection.
  ///
  /// - Parameter bounds: The range of the collection to be removed. The
  ///   bounds of the range must be valid indices of the collection.
  ///
  /// - Complexity: O(*n*), where *n* is the length of the collection.
  @inlinable
  public mutating func removeSubrange<R: RangeExpression>(
    _ bounds: R
  ) where R.Bound == Index  {
    removeSubrange(bounds.relative(to: self))
  }

但是，我在demo中下符号断点replaceSubrange，运行之后没有进来。所以这里走的是第二种实现。但是，这里并不能知道他是如何移除首个元素的。希望有了解的大神指点迷津。

但Complexity是O(n)是可以确定的。那么我接着去探究吧。

探究源码

源码如下，也不是很多，就全部贴上来了。

struct Queue<T>: Sequence {
    /// Type of generator.
    typealias Generator = AnyIterator<T>

    private let _resizeFactor = 2
    
    private var _storage: ContiguousArray<T?>
    private var _count = 0
    private var _pushNextIndex = 0
    private let _initialCapacity: Int

    /**
    Creates new queue.
    
    - parameter capacity: Capacity of newly created queue.
    */
    init(capacity: Int) {
        _initialCapacity = capacity

        _storage = ContiguousArray<T?>(repeating: nil, count: capacity)
    }
    
    private var dequeueIndex: Int {
        let index = _pushNextIndex - count
        return index < 0 ? index + _storage.count : index
    }
    
    /// - returns: Is queue empty.
    var isEmpty: Bool {
        return count == 0
    }
    
    /// - returns: Number of elements inside queue.
    var count: Int {
        return _count
    }
    
    /// - returns: Element in front of a list of elements to `dequeue`.
    func peek() -> T {
        precondition(count > 0)
        
        return _storage[dequeueIndex]!
    }
    
    mutating private func resizeTo(_ size: Int) {
        var newStorage = ContiguousArray<T?>(repeating: nil, count: size)
        
        let count = _count
        
        let dequeueIndex = self.dequeueIndex
        let spaceToEndOfQueue = _storage.count - dequeueIndex
        
        // first batch is from dequeue index to end of array
        let countElementsInFirstBatch = Swift.min(count, spaceToEndOfQueue)
        // second batch is wrapped from start of array to end of queue
        let numberOfElementsInSecondBatch = count - countElementsInFirstBatch
        
        newStorage[0 ..< countElementsInFirstBatch] = _storage[dequeueIndex ..< (dequeueIndex + countElementsInFirstBatch)]
        newStorage[countElementsInFirstBatch ..< (countElementsInFirstBatch + numberOfElementsInSecondBatch)] = _storage[0 ..< numberOfElementsInSecondBatch]
        
        _count = count
        _pushNextIndex = count
        _storage = newStorage
    }
    
    /// Enqueues `element`.
    ///
    /// - parameter element: Element to enqueue.
    mutating func enqueue(_ element: T) {
        if count == _storage.count {
            resizeTo(Swift.max(_storage.count, 1) * _resizeFactor)
        }
        
        _storage[_pushNextIndex] = element
        _pushNextIndex += 1
        _count += 1
        
        if _pushNextIndex >= _storage.count {
            _pushNextIndex -= _storage.count
        }
    }
    
    private mutating func dequeueElementOnly() -> T {
        precondition(count > 0)
        
        let index = dequeueIndex

        defer {
            _storage[index] = nil
            _count -= 1
        }

        return _storage[index]!
    }

    /// Dequeues element or throws an exception in case queue is empty.
    ///
    /// - returns: Dequeued element.
    mutating func dequeue() -> T? {
        if self.count == 0 {
            return nil
        }

        defer {
            let downsizeLimit = _storage.count / (_resizeFactor * _resizeFactor)
            if _count < downsizeLimit && downsizeLimit >= _initialCapacity {
                resizeTo(_storage.count / _resizeFactor)
            }
        }

        return dequeueElementOnly()
    }
    
    /// - returns: Generator of contained elements.
    func makeIterator() -> AnyIterator<T> {
        var i = dequeueIndex
        var count = _count

        return AnyIterator {
            if count == 0 {
                return nil
            }

            defer {
                count -= 1
                i += 1
            }

            if i >= self._storage.count {
                i -= self._storage.count
            }

            return self._storage[i]
        }
    }
}

初始化

在RxSwift内部使用ContiguousArray的实例_storage来保存队列的元素。_storage的初始容量_initialCapacity在init方法传入

init(capacity: Int) {
        _initialCapacity = capacity

        _storage = ContiguousArray<T?>(repeating: nil, count: capacity)
    }

随着元素进队列和出队列，数组 _storage 的容量可能会改变（数组的扩容和缩容），所以用 _initialCapacity 来记录数组的容量。

思考：ContiguousArray是什么？，和Array有什么关系？为什么不直接用Array?

答案在这里

在这里

我就不多啰嗦了

入队（enqueue）

mutating func enqueue(_ element: T) {
        if count == _storage.count {
            resizeTo(Swift.max(_storage.count, 1) * _resizeFactor)
        }
        
        _storage[_pushNextIndex] = element
        _pushNextIndex += 1
        _count += 1
        
        if _pushNextIndex >= _storage.count {
            _pushNextIndex -= _storage.count
        }
    }

步骤：

• 1、检测当前入队的元素的个数是否等于当前数组的容量，达到了就进行扩容（重新开辟双倍于当前容量的内存，并将当前元素拷贝到新的数组当中，这个过程后面会有详细讲解）。
• 2、将新入队元素添加到当前入队索引处，入队索引以_pushNextIndex表示，默认值为0。接着入队索引后移、入队元素个数加1。
• 3、如果当前入队索引大于等于当前数组容量。则说明队列中有的元素已经出队。在数组的开头出空出了位置，则将进入队索引 _pushNextIndex 指向数组的索引为 0 处。不然则可以继续向数组后面的位置添加元素。

出队（dequeue）

mutating func dequeue() -> T? {
        if self.count == 0 {
            return nil
        }

        defer {
            let downsizeLimit = _storage.count / (_resizeFactor * _resizeFactor)
            if _count < downsizeLimit && downsizeLimit >= _initialCapacity {
                resizeTo(_storage.count / _resizeFactor)
            }
        }

        return dequeueElementOnly()
    }
    
private mutating func dequeueElementOnly() -> T {
        precondition(count > 0)
        
        let index = dequeueIndex

        defer {
            _storage[index] = nil
            _count -= 1
        }

        return _storage[index]!
    }

步骤

• 1、有效性校验，当前队列没元素时，返回nil
• 2、根据出队索引取出出队元素，将出队索引位置处的元素置为nil，数组个数_count减一。返回出队元素。
• 3、检测当前已入队的元素小于数组容量的四分之一并且数组的初始容量小于当前数组容量的四分之一
  （_count < _storage.count / (_resizeFactor * _resizeFactor) && _storage.count / (_resizeFactor * _resizeFactor) >= _initialCapacity）
  则重新设置数组的容量为现有的一半。

出队索引计算如下:

private var dequeueIndex: Int {
        let index = _pushNextIndex - count
        return index < 0 ? index + _storage.count : index
    }

当入队索引_pushNextIndex大于当前数组的元素个数时，等于入队索引减去当前数组的元素个数（_pushNextIndex-count）

当入队索引_pushNextIndex小于当前数组的元素个数时，则出队索引为入队索引加上数组容量和当前元素的个数的差值（_pushNextIndex+_storage.count-count）

入队和出队的过程如下图：

image

重新数组容量设置容量

mutating private func resizeTo(_ size: Int) {
        /// 创建一个新的数组
        var newStorage = ContiguousArray<T?>(repeating: nil, count: size)
        
        let count = _count
        
        let dequeueIndex = self.dequeueIndex
        /// 计算数组容量和出队的位置dequeueIndex之间的间隔
        let spaceToEndOfQueue = _storage.count - dequeueIndex
        
        // first batch is from dequeue index to end of array
        /// 第一块的元素个数为 spaceToEndOfQueue 和 _count 中较小的一个
        let countElementsInFirstBatch = Swift.min(count, spaceToEndOfQueue)
        // second batch is wrapped from start of array to end of queue
        /// 第二块的元素个数为元素的个数 _count 减去 countElementsInFirstBatch 的数量
        let numberOfElementsInSecondBatch = count - countElementsInFirstBatch
        
        /// 拷贝第一块的元素
        newStorage[0 ..< countElementsInFirstBatch] = _storage[dequeueIndex ..< (dequeueIndex + countElementsInFirstBatch)]
        /// 拷贝第二块的元素
        newStorage[countElementsInFirstBatch ..< (countElementsInFirstBatch + numberOfElementsInSecondBatch)] = _storage[0 ..< numberOfElementsInSecondBatch]
        
        _count = count
        /// 重新设置入队位置
        _pushNextIndex = count
        /// 将新数组拷贝到原来的数组
        _storage = newStorage
    }

步骤：

• 1、重新创建一个容量为size的数组ContiguousArray.
• 将原来数组中的元素复制到新的数组当中。
  由上面gif图可以看出重置数组容量时，队列中的元素分布可能有两种情况

第一种情况：dequeueIndex < _pushNextIndex,此时元素分布为一整块。

image

第二种情况：dequeueIndex > _pushNextIndex, 此时元素分布为两个大块。第一块为数组开始到_pushNextIndex,第二块为dequeueIndex到数组结束。

image

具体计算看我上面代码中加的注释

我觉得作者的方式好绕啊（可能是自己没理解透彻），自己也实现了一遍。如下：

mutating private func resizeTo(_ size: Int) {
        /// 创建一个新的数组
        var newStorage = ContiguousArray<T?>(repeating: nil, count: size)
        
        let count = _count
        
        let dequeueIndex = self.dequeueIndex
        /// 当出队索引小于入队索引时，说明队列中元素只有一块
        if dequeueIndex < _pushNextIndex {
            newStorage[dequeueIndex..<_pushNextIndex] = _storage[dequeueIndex..<_pushNextIndex]
        }else {
            /// 当出队索引大于入队索引时，说明队列中元素有两块，
            /// 第一块为数组开始的位置到入队索引的位置。
            /// 第二块为出队索引到数组元素总个数减去第一块的元素个数
            newStorage[0..<_pushNextIndex] = _storage[0..<_pushNextIndex]
            newStorage[dequeueIndex..<_storage.count-_pushNextIndex] = _storage[dequeueIndex..<_storage.count-_pushNextIndex]
        }
        _count = count
        /// 重新设置入队位置
        _pushNextIndex = count
        /// 将新数组拷贝到原来的数组
        _storage = newStorage
    }

其他

    /// - returns: Is queue empty.
    var isEmpty: Bool {
        return count == 0
    }
    
    /// - returns: Number of elements inside queue.
    var count: Int {
        return _count
    }
    
    /// - returns: Element in front of a list of elements to `dequeue`.
    func peek() -> T {
        precondition(count > 0)
        
        return _storage[dequeueIndex]!
    }
    /// - returns: Generator of contained elements.
    /// 迭代器
    func makeIterator() -> AnyIterator<T> {
        var i = dequeueIndex
        var count = _count

        return AnyIterator {
            if count == 0 {
                return nil
            }

            defer {
                count -= 1
                i += 1
            }

            if i >= self._storage.count {
                i -= self._storage.count
            }

            return self._storage[i]
        }
    }
    

总结：

• RxSwift-Queue相比于我们的一般实现的enqueue的Complexity是一样的。
• RxSwift-Queue的dequeue的Complexity优于我们的一般实现。
• 一般实现的dequeue不会缩小已分配给数组的容量。RxSwift-Queue这里做了优化

有不正确的地方，欢迎指正。