博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
RxSwift Queue 队列的实现
阅读量:6038 次
发布时间:2019-06-20

本文共 4115 字,大约阅读时间需要 13 分钟。

在 RxSwift 的框架中,在 Queue.swift 文件中使用数组实现了一个队列(先进先出FIFO)。在操作次数达到 N 时,入栈和出栈的复杂度为 O(1),获取第一个出栈元素的复杂度也为 O(1)。

下面是根据源码,梳理的实现原理:

Queue 的内部使用数组 _storage 来保存队列中的元素,_storage 的初始容量在 Queue 的初始化方法中传入。

init(capacity: Int) {    _initialCapacity = capacity    _storage = ContiguousArray
(repeating: nil, count: capacity)}复制代码

随着元素进队列和出队列,数组 _storage 的容量可能会改变,所以用 _initialCapacity 来记录数组的初始化容量。

当有元素进入队列时,就从数组 _storage 的索引为 0 处向后保存。入队列的元素保存在数组 _storage 中的索引,使用属性 _pushNextIndex 来表示。当有元素出队列时,就从数组 _storage 的索引为 0 处向后获取,使用 dequeueIndex 属性来表示首先要出栈的元素在数组 _storage 中的索引。在元素入队列和出队列的过程中,使用属性 _count 来记录当前栈中元素的数量。

当有元素入队列时,如果队列中的元素数量 _count 小于数组 _storage 的容量 _storage.count,也就是说数组中还有空间可以继续存储新的队列元素。这时如果 _pushNextIndex 小于 _storage.count,则将 _pushNextIndex 不断增加,如果 _pushNextIndex 大于等于 _storage.count,则说明队列中有的元素已经出栈,在数组的开头处空出了位置,则将进入队列的索引 _pushNextIndex 指向数组的索引为 0 处,继续向后添加元素。 所以数组中的元素排布可能为以下两种情况:

  • dequeueIndex 在 _pushNextIndex 的左边,dequeueIndex = _pushNextIndex - _count
  • dequeueIndex 在 _pushNextIndex 的右边,dequeueIndex = _pushNextIndex + _storage.count - _count

所以 dequeueIndex 可以通过 _pushNextIndex 和 _count 推导出,代码如下:

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

当有元素进入队列时,如果队列中的元素数量 _count 等于数组 _storage 的容量(_storage.count)时,也就是说数组中已经存满了队列的元素,这时就需要一个更大的数组来存放队列元素。新的数组的容量通过原来数组的容量(数组的容量大于0时)乘以系数 _resizeFactor 计算获得。

// 元素进入队列的方法mutating func enqueue(_ element: T) {    // _storage 存储满了    if count == _storage.count {        // 将数组容量扩充至 Swift.max(_storage.count, 1) * _resizeFactor        resizeTo(Swift.max(_storage.count, 1) * _resizeFactor)    }        _storage[_pushNextIndex] = element    _pushNextIndex += 1    _count += 1        // _pushNextIndex 大于 _storage.count,将 _pushNextIndex 指向数组的开头    if _pushNextIndex >= _storage.count {        _pushNextIndex -= _storage.count    }}复制代码

怎样对保存队列元素的数组进行扩容呢?分成两步:

  1. 创建一个容量合适的新数组
  2. 将原来数组中的元素复制到新的数组中。

创建新的数组简单,我们应该怎样将原来数组中的元素拷贝到新的数组中。我们再次看队列元素在数组中的可能出现的分布情况:

可以将数组中的元素分成两块,第一块是出栈位置 dequeueIndex 到数组末尾的元素,第二块是数组开头到队列的结尾的元素。

这种情况的第二块的元素个数为0。

接下来计算两块的元素的数量。计算数组容量和出栈的位置 dequeueIndex 之间的间隔 spaceToEndOfQueue,则第一块的元素个数为 spaceToEndOfQueue 和 _count 中较小的一个,用 countElementsInFirstBatch 表示。第二块的元素个数为元素的个数 _count 减去 countElementsInFirstBatch 的数量,用 numberOfElementsInSecondBatch 表示。 接下来,只需要将第一段内的元素拷贝至新元素的开头,将第二段拷贝至新数组中第一段元素的末尾。

// 1.mutating private func resizeTo(_ size: Int) {    // 申请新数组    var newStorage = ContiguousArray
(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 // 第一段为 dequeue 的索引到数组的末尾 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}复制代码

在元素出队列的过程中,可能会出现数组中的容量远远大于队列中元素的数量,这时为了减少占用的内存空间,则需要缩小数组的大小。所以在有元素出队列时,需要根据条件判断是否需要缩小数组的大小。如果需要调整数组容量,则申请一个新的小容量数组,再将元素拷贝至新的数组中。将数组容量调小的方法和将数组调大的方法相同(都是通过调用 resizeTo(_) 方法)。

// 出栈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()}复制代码

转载地址:http://timhx.baihongyu.com/

你可能感兴趣的文章
如何用标签打印软件制作物料标识卡
查看>>
雷林鹏分享:二级目录配置CI应用
查看>>
雷林鹏分享:CodeIgniter 防止跨站请求伪造攻击
查看>>
612.1.004 ALGS4 | Elementary Sorts - 基础排序算法
查看>>
C指针(二)
查看>>
AS3.0中单例模式的实现
查看>>
CentOS 7----Apache基于域名的虚拟主机配置
查看>>
实现地图放大覆盖物出现圆,缩小到一定级别变成其他形状
查看>>
程序员工作法
查看>>
获取百度网盘真实地址
查看>>
css常见问题及技巧
查看>>
在eclipse里的 flex 没有可视化的编辑
查看>>
查看linux系统运行平台
查看>>
Exchange企业实战技巧(14)配置Exchange 2010存档邮箱
查看>>
比特币代码分析7 交易校验
查看>>
域名被墙怎么办?域名被墙案例-解决办法
查看>>
js-模块化requirejs
查看>>
多年以来,你可找到努力的动力?
查看>>
java中 Map 遍历方法
查看>>
Cisco IOU 模拟器测试感受
查看>>