无论您是排队购买自己喜欢的电影的门票，还是等待打印机打印出您的文件，队列都无处不在。队列使用先进先出(FIFO)顺序，这意味着入队的第一个元素将是第一个出列的元素。这与Stack整好相反.
/**
* 该协议描述了常用的队列操作
* enqueue：在队列后面插入一个元素。 如果操作成功，则返回true。
* dequeue：删除队列前面的元素并将其返回。
* isEmpty：检查队列是否为空。
* peek：返回队列前面的元素。
*/
public protocol Queue {
associatedtype Element
mutating func enqueue(_ element: Element) -> Bool
mutating func dequeue() -> Element?
var isEmpty: Bool { get }
var peek: Element? { get }
}
在以下部分中，学习以四种不同的方式创建队列：
- 使用数组
- 使用双向链表
- 使用环形缓冲
- 使用两个堆栈
Swift标准库带有核心集高度优化的原始数据结构，您可以使用它们来构建更高级别的抽象。 其中之一是Array，一种存储连续的有序元素列表的数据结构。 在本节中，您将使用数组来创建队列。
1. 使用数组创建队列
public struct QueueArray<T>: Queue {
private var array: [T] = []
public init() {}
}
接下来实现Queue协议
// 1 判断队列是否为空
public var isEmpty: Bool {
return array.isEmpty
}
// 2 返回队列最前面一个元素
public var peek: T? {
return array.first
}
Enqueue
添加一个元素到队列
public mutating func enqueue(_ element: T) -> Bool {
array.append(element)
return true
}
无论数组的大小如何，对元素进行排队都是O（1）操作。
屏幕快照 2018-12-10 下午9.13.13.png
在上面的示例中，注意一旦添加Mic，该数组有两个空格。
添加多个元素后，数组最终将满。 如果要使用多于分配的空间，则必须调整阵列大小以增加空间。
屏幕快照 2018-12-10 下午9.24.14.png
调整大小是O（n）操作。 调整大小需要数组分配新内存并将所有现有数据复制到新数组。 由于这种情况不常发生（由于每次都会增加一倍），复杂性仍然可以成为一个转化为O（1）的复杂化。
Dequeue
从队列中删除前面的元素
public mutating func dequeue() -> T? {
return isEmpty ? nil : array.removeFirst()
}
如果队列为空，则dequeue只返回nil。 如果没有，它将从数组前面删除元素并返回删除的元素
屏幕快照 2018-12-10 下午9.28.46.png
如上图所示从队列前面删除元素是O（n）操作。 要出列，请从数组的开头删除该元素。 这始终是线性时间操作，因为它要求数组中的所有剩余元素在内存中移位。
接下来就要验证一下使用数组来创建的队列了, 为了方便调试打印数据, 首先实现一下CustomStringConvertible协议
extension QueueArray: CustomStringConvertible {
public var description: String {
return array.description
}
}
添加一下代码在playground中
var queue = QueueArray<String>()
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue.dequeue()
queue
queue.peek
这段代码将Ray，Brian和Eric放入队列中，然后删除了Ray, 并查看了Brian，但没有删除它。
以下是基于队列实现的算法和存储复杂性的总结。 除了dequeue（）需要线性时间之外，大多数操作都是恒定时间。 存储空间也是线性的。
屏幕快照 2018-12-10 下午9.57.36.png
通过利用Swift数组实现队列是容易的。 由于O（1）追加操作，入队非常快。
但是它也存在一些缺点。 从队列前面删除元素可能效率低下，因为删除会导致所有元素向前移动一个。 这对非常大的队列影响很大。 一旦对列变满，它就必须调整大小并且可能有未使用的空间。 这可能会增加您的内存占用。
是否有可能解决这些缺点？ 让我们看一下基于链表的实现，并将其与QueueArray进行比较。
2. 使用双向链表创建队列
首先实现一个双向链表, 之前已经实现了 单链表 , 双向链表只是节点还包含了对前一个节点的引用, 具体实现如下
新建一个playground, 在source文件中新建DoublyLinkedList.swift 键入一下代码
public class Node<T> {
public var value: T
public var next: Node<T>?
public var previous: Node<T>?
public init(value: T) {
self.value = value
}
}
extension Node: CustomStringConvertible {
public var description: String {
return String(describing: value)
}
}
public class DoublyLinkedList<T> {
private var head: Node<T>?
private var tail: Node<T>?
public init() { }
public var isEmpty: Bool {
return head == nil
}
public var first: Node<T>? {
return head
}
public func append(_ value: T) {
let newNode = Node(value: value)
guard let tailNode = tail else {
head = newNode
tail = newNode
return
}
newNode.previous = tailNode
tailNode.next = newNode
tail = newNode
}
public func remove(_ node: Node<T>) -> T {
let prev = node.previous
let next = node.next
if let prev = prev {
prev.next = next
} else {
head = next
}
next?.previous = prev
if next == nil {
tail = prev
}
node.previous = nil
node.next = nil
return node.value
}
}
extension DoublyLinkedList: CustomStringConvertible {
public var description: String {
var string = ""
var current = head
while let node = current {
string.append("\(node.value) -> ")
current = node.next
}
return string + "end"
}
}
public class LinkedListIterator<T>: IteratorProtocol {
private var current: Node<T>?
init(node: Node<T>?) {
current = node
}
public func next() -> Node<T>? {
defer { current = current?.next }
return current
}
}
extension DoublyLinkedList: Sequence {
public func makeIterator() -> LinkedListIterator<T> {
return LinkedListIterator(node: head)
}
}
下面定义一下基于双向链表实现的队列class
public class QueueLinkedList<T>: Queue {
private var list = DoublyLinkedList<T>()
public init() {}
}
QueueLinkedList 遵循Queue协议, 因此要实现协议内的方法
Enqueue
添加一个元素到队列
/// 添加到队列
public func enqueue(_ element: T) -> Bool {
list.append(element)
return true
}
屏幕快照 2018-12-11 上午10.40.24.png
双向链表将更新其尾节点对新节点的上一个和下一个的引用。 这是O（1）操作。
Dequeue
从队列中移除元素
public func dequeue() -> T? {
guard !list.isEmpty, let element = list.first else {
return nil
}
return list.remove(element)
}
此代码检查列表是否为空并且队列的第一个元素是否存在。 如果没有，则返回nil。 否则，它会删除并返回队列前面的元素。
屏幕快照 2018-12-11 上午10.45.31.png
从列表的前面删除也是O（1）操作。 与数组实现相比，您不必逐个移动元素。 相反，在上图中，您只需更新链表的前两个节点之间的下一个和前一个指针。
与数组的实现相同, 也可以实现检查队列状态的协议
/// 查看队列的第一个元素
public var peek: T? {
return list.first?.value
}
/// 判断队列是否为空
public var isEmpty: Bool {
return list.isEmpty
}
测试实现的队列
var queue = QueueLinkedList<String>()
queue.enqueue("Ray")
queue.enqueue("Brian")
queue.enqueue("Eric")
queue.dequeue()
queue
queue.peek
性能总结
基于双链表的队列实现的算法和存储复杂性。
屏幕快照 2018-12-11 上午10.52.55.png
QueueArray的一个主要问题是将项目出列需要线性时间。使用链表实现，您将其减少为常量操作O（1）。您需要做的就是更新节点的上一个和下一个指针。
QueueLinkedList的主要弱点在表中并不明显。尽管有O（1）性能，但它的开销很高。每个元素都必须有额外的存储空间用于前向和后向引用。而且，每次创建新元素时，都需要相对昂贵的动态分配。相比之下，QueueArray可以更快地进行批量分配。
你能消除分配开销和主要O（1）队列吗？如果您不必担心队列长度超出固定大小，您可以使用不同的方法，如环形缓冲区。例如，你可能有一个拥有五名玩家的垄断游戏。您可以使用基于环形缓冲区的队列来跟踪接下来的转弯。接下来你将看一下环形缓冲区的实现。
3. 使用环形缓冲创建队列
在此基础上来实现队列, 与之前数组实现队列和链表一样, 同样需要继承Queue协议实现方法
public struct QueueRingBuffer<T>: Queue {
private var ringBuffer: RingBuffer<T>
public init(count: Int) {
ringBuffer = RingBuffer<T>(count: count)
}
public var isEmpty: Bool {
return ringBuffer.isEmpty
}
public var peek: T? {
return ringBuffer.first
}
public mutating func enqueue(_ element: T) -> Bool {
return ringBuffer.write(element)
}
public mutating func dequeue() -> T? {
return isEmpty ? nil : ringBuffer.read()
}
}
屏幕快照 2018-12-12 下午2.55.07.png
基于环形缓冲区的队列与链表实现具有相同的入队和出队时间复杂度。 唯一的区别是空间复杂性。 环形缓冲区具有固定大小，这意味着入队可能会失败。
到目前为止，您已经看到了三个实现，一个简单的数组，一个双向链表和一个环形缓冲区。 虽然它们看起来非常有用，但接下来您将看到使用两个堆栈实现的队列。 您将看到它的空间位置远远优于链表。 它也不需要像环形缓冲区那样的固定大小。
4. 使用两个堆栈创建队列
使用两个Stack来实现队列的方式是, 每次入栈时, 把入栈的元素放入RightStack, 每次出栈时, 把RightStack 里的元素翻转之后放入LeftStack, 然后从LeftStack的栈顶移除元素
两个堆栈示意图.png
栈队列
public struct QueueStack<T> : Queue {
private var leftStack: [T] = []
private var rightStack: [T] = []
public init() {}
}
实现Queue里的协议
// 1 O(1)
public var isEmpty: Bool {
return leftStack.isEmpty && rightStack.isEmpty
}
//2 O(1)
public var peek: T? {
return !leftStack.isEmpty ? leftStack.last : rightStack.first
}
- 判断队列是否为空
- 查看栈顶的元素, 如果leftStack不为空, 则leftStack栈顶的元素位于队列的前面, 否则, 需要将rightStack反转, rightStack的第一个元素将被至于leftStack的栈顶
Enqueue
public mutating func enqueue(_ element: T) -> Bool {
rightStack.append(element)
return true
}
这个和前面的使用数组实现队列一样, 简单的把元素添加到数组中, O(1)操作
入队列示意图.png
Dequeue
public mutating func dequeue() -> T? {
// 1
if leftStack.isEmpty {
//2
leftStack = rightStack.reversed()
//3
rightStack.removeAll()
}
//4
return leftStack.popLast()
}
- 因为leftStack存储的数据, 代表了队列的数据, 所以, 判断下加leftStack 是否为空, 如果为空, 则让rightStack 数据反转, 赋值给leftStack, 然后清空rightStack, 这是在leftStack及stack上, 移除栈顶的数据; 如果不为空, 则直接移除栈顶的数据
注意, 这里的返回值是T?, 因为如果leftStack和RightStack如果同时都没有数据的话, 执行了出栈操作, 返回值将会是nil, 整好利用了可选类型的数据特点
var queue = QueueStack<String>()
queue.enqueue("Ray") // true
queue.enqueue("Brian") //true
queue.enqueue("Eric") //true
queue.dequeue() //Ray
queue.peek // Brian
基于双栈实现的队列的存储读取性能, 实现了入队和出队都是O(1), 反转数组是O(n)
基于双栈实现的队列的存储读取性能
与基于数组的实现相比，通过利用两个堆栈，您可以将dequeue（_ :)转换为分摊的O（1）操作。
此外，您的两个堆栈实现是完全动态的，并且没有基于环形缓冲区的队列实现具有的固定大小限制。
最后，它在空间局部性方面胜过链表。 这是因为数组元素在内存块中彼此相邻。 因此，在第一次访问时，大量元素将被加载到缓存中。
网友评论