数据结构和算法：队列（Queue）

一、什么是队列

队列是一种表（list），但是你只能把最新的元素插到最后，或者移除最前面的元素。

我们把这种特征成为先进先出（FIFO），先加入队列的元素会最先被移出队列。

类似的数据结构是栈，与队列不同的是，栈的元素操作顺序是后进先出（LIFO）。

                              ^
                              |
┏━━━━━━┓ ┏━━━━━━┓ ┏━━━━━━┓ ┏━━━━━━┓ ┏━━━━━━┓
┃      ┃ ┃  10  ┃ ┃  10  ┃ ┃  10  ┃ ┃   3  ┃
┃      ┃ ┃      ┃ ┃  3   ┃ ┃  3   ┃ ┃  57  ┃
┃      ┃ ┃      ┃ ┃      ┃ ┃  57  ┃ ┃      ┃
┗━━━━━━┛ ┗━━━━━━┛ ┗━━━━━━┛ ┗━━━━━━┛ ┗━━━━━━┛
   ^         ^       ^
   |         |       |
   10        3       57

图 1. 队列

队列的种类：

  • 双端队列（Deque）：两端都可以入队、出队
  • 优先队列（Priority queue）：一种有序队列，最重要的元素始终放在最前面

二、为什么使用队列（队列的特点）

当你在处理一组数据时，需要考虑添加和移除元素的顺序，而且需要先进先出这种处理机制，此时就可以用到队列。

三、复杂度

1. enqueue 的复杂度：O(1)

因为每次添加一个元素到队列时，都是添加到数组的最后，而不管数组有多大，添加元素到数组最后的耗时都是一个常量。

延伸：为什么添加元素到数组后面的复杂度是 O(1)或者一个耗时为常量的操作？

因为在 Swift 的实现中，数组的末尾总是会有空余的空间，比如，现在有这样一个数组：

["Ada", "Steve", "Tim"]

在内存中，它实际上是这样的：

[ "Ada", "Steve", "Tim", xxx, xxx, xxx ]

xxx 就是暂时分配了内存但是没有用到的单元，如果添加了一个新元素，新添加的元素就会占用一个空白的内存单元：

[ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]

边界情况：但是数组末尾分配的空余空间是有限的，当最后一个 xxx 也被用了的话，如果你还要添加新的元素到数组中，你就需要重新调整数组的大小。调整数组的大小意味着需要分配新的内存空间给一个新数组，并且将原来的数组元素全部拷贝到新数组中。这个时候的操作就是一个复杂度为 O(n) 的操作，但是这只是一种极端情况，所以可以说一般情况下，添加新元素到数组的最后还是 O(1) 的操作。

2. dequeue 的复杂度为 O(n)

因为每次移除元素时，都是将数组中的第一个元素移除，然后再将后面剩余的元素往前移
比如在上面的例子中，当将 Ada 从队列中移除时，后面的 Steve 将会被拷贝到原来 Ada 的位置，Tim 将会被拷贝到原来 Steve 的位置 ...， 以此类推。

before   [ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]
                   /       /      /
                  /       /      /
                 /       /      /
                /       /      /
after    [ "Steve", "Tim", "Grace", xxx, xxx, xxx ]

遗留问题

  • 数组在内存中是如何布局的？
  • 从数组中移除第一个元素后，数组后面的元素发生了什么变化？

四、队列的实现

实现队列的方式有多种：

  • 基于数组（Array）
  • 基于链表（Linked List）
  • 基于环形缓存器（Circular Buffer）
  • 基于堆（Heap）

这里我们只讨论基于最基本的数组来实现。

1. 基本实现

我们可以基于数组来实现一个基本的队列结构，这个队列支持以下几种接口：

  • count：元素个数
  • isEmpty：是否为空
  • front：第一个元素
  • enqueue：加入元素到队列
  • dequeue：从队列中移除元素

(1) Swift 版本的实现

/// 基于数组封装的队列
public struct Queue<T> {
    var array = [T]()
    
    // 是否为空
    public var isEmpty: Bool {
        return array.isEmpty
    }
    
    // 元素个数
    public var count: Int {
        return array.count
    }
    
    // 加入队列
    public mutating func enqueue(_ element: T) {
        array.append(element)
    }
    
    // 移除队列
    public mutating func dequeue() -> T? {
        if array.isEmpty {
            return nil
        } else {
            return array.removeFirst()
        }
    }
    
    // 首元素
    public var front: T? {
        return array.first
    }
    
}

(2) Objective-C 版本的实现

Queue.h

@interface Queue<ObjectType> : NSObject

@property (assign, nonatomic, readonly) NSUInteger count;
@property (assign, nonatomic, readonly) BOOL isEmpty;
@property (strong, nonatomic, readonly) ObjectType front;

- (ObjectType)dequeue;
- (void)enqueueObject:(ObjectType)object;

@end

Queue.m

@interface Queue ()

@property (strong, nonatomic) NSMutableArray *array;

@end

@implementation Queue

- (instancetype)init {
    self = [super init];
    if (self) {
        _array = [NSMutableArray array];
    }
    return self;
}

- (BOOL)isEmpty {
    return (self.count == 0);
}

- (NSUInteger)count {
    return self.array.count;
}

- (id)front {
    if (self.count == 0) {
        return nil;
    }
    
    return self.array.firstObject;
}

- (id)dequeue {
    if (self.array.count == 0) {
        return nil;
    }
    
    id objectToRemove = self.array.firstObject;
    [self.array removeObjectAtIndex:0];
    
    return objectToRemove;
}

- (void)enqueueObject:(id)object {
    [self.array addObject:object];
}

- (NSString *)description {
    
    NSMutableString *string = [NSMutableString string];
    [string appendString:@"Queue: ["];
    for (id <NSObject> element in self.array) {
        if (element != self.array.firstObject) {
            [string appendString:@", "];
        }
        
        [string appendString:element.description];
    }
    
    [string appendString:@"]"];
    
    return string;
}

@end

2. 更高效的队列

借鉴 Swift 中数组末尾预留内存的思路，我们可以 dequeue 时通过在数组前面保留一些空余内存空间，来提高队列的 dequeue 操作的效率。

其核心思想是：当我们从队列中移除一个元素后，我们会通过将这个元素在数组中的位置标记为空，来保证后面的元素在内存中的位置不发生改变。

比如，我们有这样一个数组：

[ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]
   head

移除第一个元素 Ada 后，变成这样：

[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]
         head

移除第二个元素 Steve 后，就变成这样

[ xxx, xxx, "Tim", "Grace", xxx, xxx ]
             head

因为数组前面的空白单元都没有被重用，所以我们可以在某个时间点，再将数组中所有的元素都往前移，然后就变成这样

["Tim", "Grace", xxx, xxx ]
  head

这种操作的复杂度为 O(n)，但是因为只是偶尔才出现一次，所以总的复杂度平均下来还是 O(1)。

(1) Swift 版本的实现

/// 更高效的队列
public struct EfficientQueue<T> {
    fileprivate var array = [T?]()   // 数组中的数据类型为 optional，因为会有 nil
    fileprivate var headIndex = 0    // 标记第一个真实元素的位置
    
    
    // 是否为空
    public var isEmpty: Bool {
        return (count == 0)
    }
    
    // 元素个数
    public var count: Int {
        return (array.count - headIndex)
    }
    
    // 加入队列
    public mutating func enqueue(_ element: T) {
        array.append(element)
    }
    
    
    // 移除队列
    public mutating func dequeue() -> T? {
        // 异常处理，记录要移除的元素
        guard array.count > headIndex, let elementToRemove = array[headIndex] else {
            return nil
        }
        
        // 移除元素
        array[headIndex] = nil // 将要移除的元素的空间设为 nil
        headIndex += 1         // head 索引加 1
        
        // 定期调整元素位置
        let percentage = Double(headIndex) / Double(array.count)
        let triggerCount = 50
        if array.count > triggerCount, percentage > 0.25 {  //    或者其他条件：    if headIndex > 2 {
            array.removeFirst(headIndex)    // 移除前 headIndex 个元素
            headIndex = 0                   // 重置真实 head 索引值
        }
        
        return elementToRemove
    }
    
    // 首元素
    public var front: T? {
        // 先判断是否为空
        if isEmpty {
            return nil
        } else {
            return array[headIndex]
        }
    }
    
}

(2) Objective-C 版本的实现

EfficientQueue.h

@interface EfficientQueue<ObjectType> : NSObject

@property (assign, nonatomic, readonly) NSUInteger count;
@property (assign, nonatomic, readonly) BOOL isEmpty;
@property (strong, nonatomic, readonly) ObjectType front;

- (ObjectType)dequeue;
- (void)enqueueObject:(ObjectType)object;

@end

EfficientQueue.m


@interface EfficientQueue ()

@property (strong, nonatomic) NSMutableArray *array;
@property (assign, nonatomic) NSInteger headIndex;

@end

@implementation EfficientQueue

- (instancetype)init {
    self = [super init];
    if (self) {
        _array = [NSMutableArray array];
        _headIndex = 0;
    }
    return self;
}

- (BOOL)isEmpty {
    return (self.count == 0);
}

- (NSUInteger)count {
    return self.array.count - self.headIndex;
}

- (id)front {
    if (self.isEmpty) {
        return nil;
    }
    
    return self.array[self.headIndex];
}

- (id)dequeue {
    if (self.isEmpty) {
        return nil;
    }
    
    // 移除
    id objectToRemove = self.front;
    self.array[self.headIndex] = [NSNull null];
    self.headIndex++;
    
    // 定期清理空值
    double percentage = self.headIndex / (double)(self.array.count);
    if (percentage > 0.25 && self.count > 100) {
        [self.array removeObjectsInRange:NSMakeRange(0, self.headIndex)];
        self.headIndex = 0;
    }
    
    return objectToRemove;
}

- (void)enqueueObject:(id)object {
    [self.array addObject:object];
}

- (NSString *)description {
    
    NSMutableString *string = [NSMutableString string];
    [string appendString:@"EfficientQueue: ["];
    
    for (id <NSObject> element in self.array) {
        if ([element isKindOfClass:[NSNull class]]) {
            continue;
        }
        
        if (element != self.front) {
            [string appendString:@", "];
        }
        
        [string appendString:element.description];
    }
    
    [string appendString:@"]"];
    
    return string;
}

@end

五、队列的应用

在经典的 iOS 图片下载框架 SDWebImage 中，SDWebImageDownloader 类里面就通过一个 executionOrder 来决定下载队列中下载任务的先后顺序，是 FIFO，还是 LIFO。

六、我所理解的队列

  • 队列是一种表
  • 队列的元素操作顺序是先进先出（FIFO）

七、相关面试题（TODO）

八、参考资料

如果你也喜欢交流技术、喜欢阅读、积极践行，欢迎关注我的公众号：祥龙Shannon写字的地方，一起成长。

qrcode_for_gh_cc686217be41_344.jpg
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,098评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,213评论 2赞 380
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 149,960评论 0赞 336
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,519评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,512评论 5赞 364
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,533评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,914评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,574评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,804评论 1赞 296
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,563评论 2赞 319
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,644评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,350评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,933评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,908评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,146评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,847评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,361评论 2赞 342

推荐阅读更多精彩内容

  • Swift数据结构－队列Queue
    声明：算法和数据结构的文章均是作者从github上翻译过来，为方便大家阅读。如果英语阅读能力强的朋友，可以直接到s...
    UnsanYL阅读 6,052评论 2赞 5
  • 优秀第三方
    发现 关注 消息 iOS 第三方库、插件、知名博客总结 作者大灰狼的小绵羊哥哥关注 2017.06.26 09:4...
    肇东周阅读 12,016评论 4赞 62
  • 命
    如果这是命，我认了，相信明天会更好！
    mountebank阅读 196评论 0赞 0