100天iOS数据结构与算法实战 Day10 - 队列

栏目: 编程工具 · 发布时间: 5年前

内容简介:队列的特性先进先出,俗称FIFO。

队列的特性

先进先出,俗称FIFO。

我们来大致描述下进出队列的情况。

100天iOS数据结构与算法实战 Day10 - 队列 有几个注意的地方。

1:如果队列里没有元素将返回nil ,可以给一个错误提示信息。 2:进队列的时间复杂度是O(1),因为随着数组的增加不会影响时间复杂度,只是在最后面添加。但是如果这个数组的容量占满了,那么我们得重新调整数组容量来获取更多的空间,这个操作是重新创建新的内存,然后再copy,这个时间复杂度是O(n) 。 3: 我们假设iOS的数组不是circular buffer来实现,我们考虑下这个情况,注意后面说的数组都是非circular buffer结构实现的 。那么队列从头部出队列,后面元素内存要移位操作。这个是一个时间复杂度为O(n)操作。所以我们不能在数组中删除第一个元素,因为删除后,一般数组的机制为了填充前面的空隙后面的元素会前移,所以我们只是返回要出队的元素。

先看没有优化前的队列的代码

进队的代码

  1. - (void)enqueue:(id)object

  2. {

  3.    if (object != nil) {

  4.        [self.queueArray addObject:object];

  5.    }

  6.    else {

  7.        NSAssert(object != nil, @"You can't push nil object to queue");

  8.    }

  9. }

出队的代码

  1. - (id)dequeue

  2. {

  3.    if ([self.queueArray count] > 0)

  4.    {

  5.        id object = [self peek];

  6.        [self.queueArray removeObjectAtIndex:0];

  7.        return object;

  8.    }

  9.    return nil;

  10. }

如果队列存在元素才能出去,但是如果删除第一个元素,后面元素前移(上面也说了这是数组的机制为了填充前面的空隙)影响效率,我们后面会优化这个地方。

优化后的代码

为了充分利用数组的空间,并且避免频繁的移动元素,不直接删除头部元素,而是置为空,通过移动索引的方式返回要出队的元素,当队列的头部索引前面的空间比较大的时候我们清理一波。

  1. - (id)dequeue

  2. {

  3.    id object;

  4.    if (self.headIndex < self.queueArray.count)

  5.    {

  6.        object = self.queueArray[self.headIndex];

  7.    }

  8.    else

  9.    {

  10.        return nil;

  11.    }

  12.    self.queueArray[self.headIndex] = [NSNull null];

  13.    self.headIndex += 1;

  14.    double percentage = (double)self.headIndex/(double)(self.queueArray.count);

  15.    if (self.queueArray.count > kQueueCapacity && percentage > 0.25)

  16.    {

  17.        [self.queueArray removeObjectsInRange:NSMakeRange(0, self.headIndex)];

  18.        self.headIndex = 0;

  19.    }

  20.    return object;

  21. }

上面计算了队首空余的元素占数组总元素的百分比,如果空余元素超过 25%,我们就进行一波清理。但是,如果队列的长度过小,我们也不想频繁地清理空间,所以在清理空间之前,队列中至少要有 一定量 的元素,比如我这个kQueueCapacity 是 100。

测试结果

进队

    DSQueue *queue = [[DSQueue alloc] initWithSize:5];    [queue enqueue:@"1"];    [queue enqueue:@"2"];    [queue enqueue:@"3"];    [queue enqueue:@"4”];

结果图

100天iOS数据结构与算法实战 Day10 - 队列

出队

 [queue dequeue];

结果图

100天iOS数据结构与算法实战 Day10 - 队列

清空前面的占位元素节省空间

100天iOS数据结构与算法实战 Day10 - 队列

看箭头所指的地方现在索引前面的多余的空间已经被清理了,并且索引的是0。

还有优化的空间

  • 之前我们说栈的时候动态扩容,提过频繁创建copy的扩容操作。

  • 我们可以利用头部的空间,不清理它,比如队尾巴满了,头部有空间我们可以放到头部,这样加一个尾部索引,如果头部和尾部索引真相等了那么,这个队列可能真满了,再考虑创建更多的空间。

  • 由于队列的顺序性,我们要小心copy元素,比如如果头部元素大于尾部元素那么就是copy从头部元素一直到size个元素到新的数组,如果头部元素小于尾部元素就要copy两部分元素,头部元素到数组结束的元素,还有一部分数组开始到尾部索引的元素到新的数组。

总结

通过移动索引的方式来避免移动元素,通过一定的机制清理多余的空间来节省内存。现在在数组非circular buffer实现情况下出队操作的复杂度已经从之前的 O(n) 变为了现在的 O(1),由于iOS数组采用的circular buffer这个结构所以避免了出队操作造成移动较多元素的问题。

GithubDemo

https://github.com/renmoqiqi/100-Days-Of-iOS-DataStructure-Algorithm/tree/master/Day10

转载自公众号:人魔七七


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

思考,快与慢

思考,快与慢

[美] 丹尼尔·卡尼曼 / 胡晓姣、李爱民、何梦莹 / 中信出版社 / 2012-7 / 69.00元

《纽约时报》2011年度十大好书 新书上市,连续20多周蝉联亚马逊、《纽约时报》畅销书排行榜前20名,上市至今超过7个月,横扫全球各大畅销书排行榜,稳居亚马逊总榜前50名 《经济学人》、《华尔街日报》、《卫报》、《纽约时报》、《金融时报》、《商业周刊》、《华盛顿邮报》、等国外权威媒体,《三联生活周刊》、《商学院》、《东方早报》等国内知名媒体争相报道,国内外读者好评如潮 人类究竟有......一起来看看 《思考,快与慢》 这本书的介绍吧!

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具