博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Swift算法俱乐部:Swift队列数据结构(Queue)
阅读量:5868 次
发布时间:2019-06-19

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

准备开始

队列(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实现来实现队列。 在花括号之间添加以下内容:

// 1fileprivate var list = LinkedList
()// 2public mutating func enqueue(_ element: Int) { list.append(element)}
  1. 添加了一个fileprivate LinkedList变量,用于将这些项目存储在队列中。
  2. 已经添加了一个方法来排列项目。 这个方法会改变底层的LinkedList,所以明确地指定了在方法前加上mutating关键字。

出列(Dequeue)

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

// 1public mutating func dequeque() -> Int? {    // 2    guard !list.isEmpty, let element = list.first else { return nil}        list.remove(element)        return element.value}
  1. 添加一个返回队列中第一个项目的出队方法。 返回类型可以为空来处理队列为空。
  2. 使用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类的实现下方添加以下内容:

// 1extension Queue: CustomStringConvertible {    // 2    public var description: String {        // 3        return list.description    }}
  1. 声明Queue类的扩展,让它遵循CustomStringConvertible协议。 该协议期望使用字符串类型实现带名称描述的计算属性。
  2. 声明了description属性。 这是一个计算属性,它是一个返回String的只读属性。
  3. 返回基于LinkedList的描述。

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

[10, 3, 57]

Swift通用队列实现

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

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

// 1public 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)

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

本系列其他文章:

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

你可能感兴趣的文章
Changing Your Commit Messages
查看>>
java.lang.IncompatibleClassChangeError
查看>>
CSS3学习资料
查看>>
cocos官网例子
查看>>
python list extend(扩展) append(添加)
查看>>
如何降低android应用程序的耗电量
查看>>
php 正则匹配中文 utf8编码/^[\x{4e00}-\x{9fa5}A-Za-z0-9_]+$
查看>>
MySQL查看和修改表的存储引擎
查看>>
iframe子页面调用父页面隐藏域的值
查看>>
redis系列(入门,jedis,spring+get/set/del+hmget/hmset+列表)
查看>>
Java多态性理解
查看>>
定期删除elasticsearch的过期index
查看>>
订单突破10000+,仅花1小时,APPx独家深入剖析背后的秘密!
查看>>
Mybits xml 配置需要注意的地方
查看>>
Django 笔记-20190524
查看>>
调试U-Boot笔记(九)-- NorFlash芯片说明摘抄
查看>>
技术写作是有技巧的
查看>>
clojure的参数分解,Binding Forms (Destructuring)
查看>>
$("data_list").src="shareEmergencyGroup!doQuery.action?id="+${id};不访问action
查看>>
iOS 调试心得
查看>>