数据结构:Queue

分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看272 回复回复5 收藏收藏 分享淘帖 转播转播 分享分享 微信
查看: 272|回复: 5
收起左侧

数据结构:Queue

[复制链接]
Ding 发表于 2016-11-3 16:51:00 | 显示全部楼层 |阅读模式
快来登录
获取优质的苹果资讯内容
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
订阅梳理好了的知识点专辑
队列(Queue)是另一个类似Array但是相当内敛的闺秀,是栈(Stack)的妹妹,听说她最近当了王后(Queen)~

和栈的先来后走正相反,她崇尚的是先来先走。

只能在队列尾部进(enqueue)一个元素,在头部出(dequeue)一个元素,看(peek)也只能看头。

看例子:

[Swift] 纯文本查看 复制代码
queue.enqueue(10)   // 队列里来了第一个成员10, 队列成了[ 10 ]
queue.enqueue(3)    // 现在是[ 10, 3 ]
queue.enqueue(57)   // 现在是[ 10, 3, 57 ]

queue.dequeue()     // 最先来的那位走了,现在是[ 3, 57 ],这个函数返回走了的10
queue.dequeue()     // 返回3,现在是[ 57 ]


如果队列空了再dequeue,就会返回nil,有的实现会直接给个错误信息(“没了”)。

注:如果不是一定要先来先走,我更喜欢姐姐,栈,姐姐比妹妹更简单、高效。

我们可以像实现栈那样,对Array简单包装来实现队列:

[Swift] 纯文本查看 复制代码
public struct Queue<T> {
    fileprivate 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 isEmpty {
            return nil
        } else {
            return array.removeFirst()
        }
    }
    
    public func peek() -> T? {
        return array.first
    }
}


这个实现不错,但在效率上有些缺憾。

虽然入队是个常数级复杂度的操作,但是出队却是线性复杂度的。因为头部的元素出队后,其他所有剩余元素都需要往前移一步。

让我们尽量避免移动来修正一下:

[Swift] 纯文本查看 复制代码
public struct Queue<T> {
    fileprivate var array = [T?]()
    fileprivate var head = 0
    
    public var isEmpty: Bool {
        return count == 0
    }
    
    public var count: Int {
        return array.count - head
    }
    
    public mutating func enqueue(_ element: T) {
        array.append(element)
    }
    
    public mutating func dequeue() -> T? {
        guard head < array.count, let element = array[head] else { return nil }
        
        array[head] = nil
        head += 1
        
        let percentage = Double(head)/Double(array.count)
        if array.count > 50 && percentage > 0.25 {
            array.removeFirst(head)
            head = 0
        }
        
        return element
    }
    
    public func peek() -> T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}


现在array里的元素是T?而不是原来的T。这样我们就可以用nil来表示数组那个位置没有元素,再用head变量,保证永远代表第一个元素的索引,这样一来就避免了在出队时移动元素。

当然,如果永不真正移除数组里的那些nil,我们的王后就会像她姐栈会“爆栈”一样,“爆队”给我们看。

数据结构:Queue

数据结构:Queue - 敏捷大拇指 - 数据结构:Queue


所以我们要在适当的时候,真正移除元素,就像这段代码做的:

[Swift] 纯文本查看 复制代码
let percentage = Double(head)/Double(array.count)
if array.count > 50 && percentage > 0.25 {
    array.removeFirst(head)
    head = 0
}


算一下nil在整个array里的比例,如果大于四分之一且数组总长度大于50,就真的移除head及之前的元。

0.25啊50啊这些数字要因情况而定,具体定多少,看你。

测试一下改进后的队列:

[Swift] 纯文本查看 复制代码
var q = Queue<String>()
q.array                   // []

q.enqueue("Ada")
q.enqueue("Steve")
q.enqueue("Tim")
q.array             // [{Some "Ada"}, {Some "Steve"}, {Some "Tim"}]
q.count             // 3

q.dequeue()         // "Ada"
q.array             // [nil, {Some "Steve"}, {Some "Tim"}]
q.count             // 2

q.dequeue()         // "Steve"
q.array             // [nil, nil, {Some "Tim"}]
q.count             // 1

q.enqueue("Grace")
q.array             // [nil, nil, {Some "Tim"}, {Some "Grace"}]
q.count             // 2


改进后的队列很棒,出队操作也变成了平均情况下的常数级。

队列还有很多实现方式,比如可以基于链表(linked list)、环状缓存(circular buffer)或堆(heap)来做,或者双向链表,或者排序队列等。你能想到的,都可以燃烧一把。




原作者: Matthijs Hollemans

都看到这里了,就把这篇资料推荐给您的好朋友吧,让他们也感受一下。

回帖是一种美德,也是对楼主发帖的尊重和支持。您的赞赏是我前进的方向。

*声明:敏捷大拇指是全球最大的Swift开发者社区、苹果粉丝家园、智能移动门户,所载内容仅限于传递更多最新信息,并不意味赞同其观点或证实其描述;内容仅供参考,并非绝对正确的建议。本站不对上述信息的真实性、合法性、完整性做出保证;转载请注明来源并加上本站链接,敏捷大拇指将保留所有法律权益。如有疑问或建议,邮件至marketing@swifthumb.com

*联系:微信公众平台:“swifthumb” / 腾讯微博:@swifthumb / 新浪微博:@swifthumb / 官方QQ一群:343549891(满) / 官方QQ二群:245285613 ,需要报上用户名才会被同意进群,请先注册敏捷大拇指

评分

参与人数 1金钱 +10 贡献 +10 专家分 +10 收起 理由
Anewczs + 10 + 10 + 10 32个赞!专家给力!

查看全部评分

本帖被以下淘专辑推荐:

Anewczs 发表于 2016-11-3 17:07:22 | 显示全部楼层
看来你已经掌握好了编辑格式哈~~
 楼主| Ding 发表于 2016-11-3 17:12:48 | 显示全部楼层
Anewczs 发表于 2016-11-3 17:07
看来你已经掌握好了编辑格式哈~~

嗯。阿牛引导的结果。

i0n1c 发表于 2016-11-3 18:02:11 | 显示全部楼层
我的确想到了Queen ^_*
 楼主| Ding 发表于 2016-11-4 08:08:30 | 显示全部楼层
i0n1c 发表于 2016-11-3 18:02
我的确想到了Queen ^_*

我学生时代的迷惑~
苏格拉没有底 发表于 2016-11-4 09:16:51 | 显示全部楼层
栈,你来了我当你没走;
队列,你走了我当你没来。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

淘帖专辑
我要发帖

分享扩散

都看到这里了,就把这资料推荐给您的好朋友吧,让他们也感受一下。
您的每一位朋友访问此永久链接后,您都将获得相应的金钱积分奖励
关闭

站长推荐 上一条 /1 下一条

热门推荐

合作伙伴

Swift小苹果

  • 北京治世天下科技有限公司
  • ©2014-2016 敏捷大拇指
  • 京ICP备14029482号
  • Powered by Discuz! X3.1 Licensed
  • swifthumb Wechat Code
  •   
快速回复 返回顶部 返回列表