Swift算法俱乐部：Swift队列数据结构（Queue)

0xE7A38A 发布于2019-06-25 16:49 / 1080人阅读

摘要：队列现在将是，。这将返回下一个出列将返回，依此类推。如果队列为空，则出队将返回零。使用语句处理队列为空。要显示更可读的输出字符串，可以使队列采用协议。本系列其他文章算法俱乐部栈数据结构

翻译自raywenderlich网站iOS教程Swift Algorithm Club系列

准备开始

队列（Queue)是一个列表，您只能在后面插入新项目并从前面删除项目。这可确保入队的第一个元素也是首先出队的元素。先到先出
在许多算法中，我们希望在某个时间点将项目添加到临时列表中，然后在以后再次将它们从列表中拉出。添加和删除这些项目的顺序非常重要。

队列提供先进先出或先入先出的顺序。首先插入的元素也是第一个出来的元素（和堆栈(Stack)非常类似，是LIFO或后进先出。）

这是一个栗子
理解队列的最简单方法是看看它是如何使用的。

想象一下你有一个队列。以下是你如何入选一个数字：

queue.enqueue(10)

队列现在是[10]。然后，继续将下一个号码添加到队列中：

queue.enqueue(3)

队列现在是[10,3]。继续添加：

queue.enqueue(57)

队列现在是[10,3,57]。我们可以将队列中的第一个元素从队列中拉出：

queue.dequeue()

将返回10，因为这是插入的第一个数字。队列现在将是[3，57]。每个项目都向上移动一个地方。

queue.dequeue()

这将返回3.下一个出列将返回57，依此类推。如果队列为空，则出队将返回零。

实现队列
在本节中，将实现一个存储Int值的简单通用队列。
创建一个新的playground，添加如下代码：

public struct Queue {
    
}

playground还包含LinkedList的代码（可以通过转到查看 Project Navigators Show Project Navigator并打开Sources LinkedList来看到这一点。

入队（Enqueue）

队列需要入队方法。我们使用项目中包含的LinkedList实现来实现队列。在花括号之间添加以下内容：

// 1
fileprivate var list = LinkedList()

// 2
public mutating func enqueue(_ element: Int) {
    list.append(element)
}

添加了一个fileprivate LinkedList变量，用于将这些项目存储在队列中。

已经添加了一个方法来排列项目。这个方法会改变底层的LinkedList，所以明确地指定了在方法前加上mutating关键字。

出列（Dequeue)

队列也需要一个出队方法。

// 1
public mutating func dequeque() -> Int? {
    // 2
    guard !list.isEmpty, let element = list.first else { return nil}
    
    list.remove(element)
    
    return element.value
}

添加一个返回队列中第一个项目的出队方法。返回类型可以为空来处理队列为空。

使用guard语句处理队列为空。如果这个队列是空的，那么guard将会进入else块。

查看（Peek）

队列还需要一个peek方法，它在队列的开始处返回该项目而不删除它。

public func peek() -> Int? {
  return list.first?.value
}

IsEmpty

队列可以是空的。添加一个isEmpty属性，该属性将返回基于LinkedList的值：

public var isEmpty: Bool {
    return list.isEmpty
}

打印队列

让我们试试新队列。在队列实现下面，将以下内容写入playground中：

var queue = Queue()
queue.enqueue(10)
queue.enqueue(3)
queue.enqueue(57)

定义队列后，尝试将队列打印到控制台：

print(queue)

输出如下：

Queue(list: [10, 3, 57])

这输出的样式不是很好。要显示更可读的输出字符串，可以使队列采用CustomStringConvertable协议。为此，请在Queue类的实现下方添加以下内容：

// 1
extension Queue: CustomStringConvertible {
    // 2
    public var description: String {
        // 3
        return list.description
    }
}

声明Queue类的扩展，让它遵循CustomStringConvertible协议。该协议期望使用字符串类型实现带名称描述的计算属性。

声明了description属性。这是一个计算属性，它是一个返回String的只读属性。

返回基于LinkedList的描述。

现在控制台的输出编程如下样式：

[10, 3, 57]

Swift通用队列实现
此时，我们已经实现了一个存储Int值的通用队列，并提供了在Queue类中查看，排队和出列项目的功能。
在本节中，我们使用泛型从队列中抽象出类型需求。

将Queue类的实现更新为以下内容：

// 1
public struct Queue {
    // 2
    fileprivate var list = LinkedList()
    
    // 3
    public mutating func enqueue(_ element: T) {
        list.append(element)
    }
    
    // 4
    public mutating func dequeque() -> T? {

        guard !list.isEmpty, let element = list.first else { return nil}
        
        list.remove(element)
        
        return element.value
    }
    // 5
    public func peek() -> T? {
        return list.first?.value
    }
    
    public var isEmpty: Bool {
        return list.isEmpty
    }
}

修正测试代码如下：

var queue = Queue()
queue.enqueue(10)
queue.enqueue(3)
queue.enqueue(57)
print(queue)

还可以尝试使用不同类型的Queue：

var queue2 = Queue()
queue2.enqueue("mad")
queue2.enqueue("lad")
if let first = queue2.dequeque() {
    print(first)
}
print(queue2)

以上是本人在raywenderlich学习时为方便自己，用翻译工具翻译之后做的一个记录。

本系列其他文章：
Swift算法俱乐部：Swift栈(Stack)数据结构

云服务器私有云 swift swift21 swift webrtc swift cell

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/17065.html

Swift算法俱乐部：Swift栈(Stack)数据结构

摘要：根据设计，堆栈不允许您检查其内容，但堆栈的顶层元素除外。返回类型是可选的，以处理堆栈空置的情况。幸运的是，提供了更便捷的方法，首先，将的声明更新为以下内容将结构声明为泛型，允许堆栈将其用于所有类型。本系列其他文章算法俱乐部队列数据结构翻译自raywenderlich网站iOS教程Swift Algorithm Club系列堆栈(Stack)就像数组，但功能有限。堆栈提供LIFO或后...

yunhao 2019-06-25 16:49 评论0 收藏0
AVKit 播放（AVFoundation, AVKit, 音视频， Swift 4，配代码）

摘要：播放视频，苹果设计的很简单，代码如下拿一个建立一个实例你的再建立一个实例这里有一个闭包，出现了，再播放。苹果文档上说，用于管理播放器播放的资源的计时和呈现状态。推荐资源苹果文档视频教程大佬博客，本地网络视频播放相关音视频，简单点，上手就用，当然是 AVKit.更加灵活的控制，就要用到 AVFoundation 了。要点：使用资源（一般就是照片库里面的视频，图片，live ph...

Jenny_Tong 2019-06-25 16:56 评论0 收藏0
IOS-Swift开发基础——通知

摘要：是专门供程序中不同类间的消息通信的。使用它为我们代码降低耦合。 NSNotificationCenter NSNotificationCenter是专门供程序中不同类间的消息通信的。使用它为我们代码降低耦合。自定义数据监听注册监听： // addObserver 4个参数分别是：接受者对象，接受者处理函数，消息名称，发送者对象(通常设为nil) NSNotificationCent...

April 2019-06-25 15:09 评论0 收藏0
如何通过热修复，搞定开发中的那些 Bug？

摘要：作为程序员，修复终究是绕不开的话题，本期移动开发精英俱乐部讨论的主题便是修复中的，即热修复。王威威对已发布进行修复。王伟我们会在本地测试好，通过验证后才正式发送修复脚本。海不是简单的性能问题，如果要同时修复两个线程的方法就悲剧了。作为程序员，Bug 修复终究是绕不开的话题，本期移动开发精英俱乐部讨论的主题便是 Bug 修复中的 Hotfix，即热修复。接下来让我们跟随大牛的脚步来了解...

lcodecorex 2019-05-28 18:29 评论0 收藏0
即将立秋的《课多周刊》(第2期)

摘要：即将立秋的课多周刊第期我们的微信公众号，更多精彩内容皆在微信公众号，欢迎关注。若有帮助，请把课多周刊推荐给你的朋友，你的支持是我们最大的动力。课多周刊机器人运营中心是如何玩转起来的分享课多周刊是如何运营并坚持下来的。即将立秋的《课多周刊》(第2期) 我们的微信公众号：fed-talk，更多精彩内容皆在微信公众号，欢迎关注。若有帮助，请把课多周刊推荐给你的朋友，你的支持是我们最大...

ruicbAndroid 2019-08-29 11:06 评论0 收藏0