Swift 语言的队列实现

Question

我正在尝试在 Swift 平台中实现队列集合类型。我有一些关于 peek、poll 和 offer 函数的问题。当我尝试在我的代码中使用这些函数时，它失败了。您对此有什么建议或真正的算法吗？

import Foundation


class Node<T> {
    var value: T? = nil
    var next: Node<T>? = nil
    var prev: Node<T>? = nil

    init() {
    }

    init(value: T) {
        self.value = value
    }
}

class Queue<T> {

var count: Int = 0

var head: Node<T> = Node<T>()

var tail: Node<T> = Node<T>()

var currentNode : Node<T> = Node<T>()

    init() {
    }

    func isEmpty() -> Bool {
        return self.count == 0
    }

    func next(index:Int) -> T? {

        if isEmpty() {
            return nil
        } else if self.count == 1 {
            var temp: Node<T> = currentNode
            return temp.value
        } else if index == self.count{
            return currentNode.value

        }else {
            var temp: Node<T> = currentNode
            currentNode = currentNode.next!
            return temp.value
        }

    }

    func setCurrentNode(){
        currentNode = head
    }

    func enQueue(key: T) {
        var node = Node<T>(value: key)
        if self.isEmpty() {
            self.head = node
            self.tail = node
        } else {
            node.next = self.head
            self.head.prev = node
            self.head = node
        }

        self.count++
    }

    func deQueue() -> T? {
        if self.isEmpty() {
            return nil
        } else if self.count == 1 {
            var temp: Node<T> = self.tail
            self.count--
            return temp.value
        } else {
            var temp: Node<T> = self.tail
            self.tail = self.tail.prev!
            self.count--
            return temp.value
        }
    }



    //retrieve the top most item
    func peek() -> T? {

        if isEmpty() {
            return nil
        }

        return head.value!
    }

    func poll() -> T? {

        if isEmpty() {
            return nil
        }else{
            var temp:T = head.value!
            deQueue()
            return temp
        }

    }

    func offer(var key:T)->Bool{
        var status:Bool = false;

        self.enQueue(key)
        status = true


        return status
    }
}

Answer 1

除了 bug 之外，还有一些关于您的实现的事情您可能想要更改以使其更加 Swift-like。一个是看起来你正在复制 Java 名称，如 poll 和 offer – 这些名称（恕我直言）有点奇怪，部分与需要有两个功能有关，一个exception-throwing 版本和 non-exception 版本。由于 Swift 没有例外，您可以使用其他 Swift collection 使用的常规名称来命名它们，例如 append.

另一个问题是您的实现将遍历队列合并到队列本身中。最好在 collection 之外进行这种遍历，而不是将两者混合。 Swift collection 使用索引执行此操作。

这是一个可能的 Swift-like 队列实现。一、节点和基队列定义：

// singly rather than doubly linked list implementation
// private, as users of Queue never use this directly
private final class QueueNode<T> {
    // note, not optional – every node has a value
    var value: T
    // but the last node doesn't have a next
    var next: QueueNode<T>? = nil

    init(value: T) { self.value = value }
}

// Ideally, Queue would be a struct with value semantics but 
// I'll leave that for now
public final class Queue<T> {
    // note, these are both optionals, to handle
    // an empty queue
    private var head: QueueNode<T>? = nil
    private var tail: QueueNode<T>? = nil

    public init() { }
}

然后，使用 append 和 dequeue 方法扩展：

extension Queue {
    // append is the standard name in Swift for this operation
    public func append(newElement: T) {
        let oldTail = tail
        self.tail = QueueNode(value: newElement)
        if  head == nil { head = tail }
        else { oldTail?.next = self.tail }
    }

    public func dequeue() -> T? {
        if let head = self.head {
            self.head = head.next
            if head.next == nil { tail = nil }
            return head.value
        }
        else {
            return nil
        }
    }
}

此时，如果您只想添加和删除，那么您就差不多完成了。要添加遍历，首先创建一个索引类型，它是对节点类型的简单包装：

public struct QueueIndex<T>: ForwardIndexType {
    private let node: QueueNode<T>?
    public func successor() -> QueueIndex<T> {
        return QueueIndex(node: node?.next)
    }
}

public func ==<T>(lhs: QueueIndex<T>, rhs: QueueIndex<T>) -> Bool {
    return lhs.node === rhs.node
}

然后，使用这个索引来符合MutableCollectionType:

extension Queue: MutableCollectionType {
    public typealias Index = QueueIndex<T>
    public var startIndex: Index { return Index(node: head) }
    public var endIndex: Index { return Index(node: nil) }

    public subscript(idx: Index) -> T {
        get {
            precondition(idx.node != nil, "Attempt to subscript out of bounds")
            return idx.node!.value
        }
        set(newValue) {
            precondition(idx.node != nil, "Attempt to subscript out of bounds")
            idx.node!.value = newValue
        }
    }

    typealias Generator = IndexingGenerator<Queue>
    public func generate() -> Generator {
        return Generator(self)
    }
}

从符合 collection 类型开始，您可以免费获得一大堆东西：

var q = Queue<String>()
q.append("one")
q.append("two")

for x in q {
    println(x)
}

isEmpty(q) // returns false
first(q)   // returns Optional("one")
count(q)   // returns 2
",".join(q)  // returns "one,two"
let x = find(q, "two")  // returns index of second entry
let counts = map(q) { count([=14=]) }  // returns [3,3]

最后，还有 3 个协议值得遵守：ExtensibleCollectionType、Printable 和 ArrayLiteralConvertible:

// init() and append() requirements are already covered
extension Queue: ExtensibleCollectionType {
    public func reserveCapacity(n: Index.Distance) {
        // do nothing
    }

    public func extend<S : SequenceType where S.Generator.Element == T>
      (newElements: S) {
        for x in newElements {
            self.append(x)
        }
    }
}

extension Queue: ArrayLiteralConvertible {
    public convenience init(arrayLiteral elements: T...) {
        self.init()
        // conformance to ExtensibleCollectionType makes this easy
        self.extend(elements)
    }
}

extension Queue: Printable {
    // pretty easy given conformance to CollectionType
    public var description: String {
        return "[" + ", ".join(map(self,toString)) + "]"
    }
}

这意味着您现在可以像创建数组或集合一样轻松地创建队列：

var q: Queue = [1,2,3]
println(q)  // prints [1, 2, 3]

Answer 2

关于你的模型的内部一致性有很多小问题：

当您第一次实例化一个新的 Queue 时，您正在将 head、tail 和 current 初始化为三个不同的 Node objects（尽管还没有 queued！）。那没有意义。就个人而言，我倾向于将这三个属性设为可选，并将它们保留为 nil，直到您开始排队。

顺便说一下，当您开始对这些属性使用可选值时，许多其他方法都会得到简化。
您似乎正在尝试实现双向链表。所以，当你 dequeue 时，你不仅需要更新 Queue 属性，你还需要更新下一个将被 de[=65= 的项目的 next 指针]d（因为它仍然会指向您已经 dequeued 的项目）。您不希望您的链表保留对 object 的引用，这些引用已经被删除 queue 并且应该被删除。
当你 dequeue 最后一项时，你真的应该清除 head 和 tail 引用。
您正在实现双向链表，而不考虑 object 所有权模型。因此，一旦您的列表中有多个项目，节点之间就会有一个强大的引用循环，如果不加以补救，如果 queue 中仍然有 object，这就会泄漏当 queue 本身被释放时。考虑制作参考文献之一 weak 或 unowned.
我建议保持简单（仅 enqueue 和 dequeue）。 poll 和 offer 的概念在任意链表方面可能有意义，但在 queue 的上下文中则不然。 poll 和 offer 的实现也不正确（例如 poll 调用 deQueue 删除了尾巴，但是 object 你 return 是head!)，但我想您会完全删除这些功能。同样，在 queue.
的上下文中，我不理解 current 的意图
我建议你让 Queue 和 Node 符合 Printable。它将简化您的调试过程。

Answer 3

以下是游乐场的代码，由一个用数组实现的队列和一个用节点实现的队列组成。两者之间存在很大的性能差异，但如果您要遍历队列，您可能希望将其中一个与数组一起使用。

import UIKit // for NSDate() used in testing)

// QUEUE WITH ARRAY IMPLEMENTATION (For ease of adaptibility, slow enque, faster deque):

struct QueueArray<T> {
    private var items = [T]()

    mutating func enQueue(item: T) {
        items.append(item)
    }

    mutating func deQueue() -> T? {
        return items.removeFirst()
    }

    func isEmpty() -> Bool {
        return items.isEmpty
    }

    func peek() -> T? {
        return items.first
    }
}

// QUEUE WITH NODE IMPLEMENTATION (For performance, if all you need is a queue this is it):

class QNode<T> {
    var value: T
    var next: QNode?

    init(item:T) {
        value = item
    }
}

struct Queue<T> {
    private var top: QNode<T>!
    private var bottom: QNode<T>!

    init() {
        top = nil
        bottom = nil
    }

    mutating func enQueue(item: T) {

        let newNode:QNode<T> = QNode(item: item)

        if top == nil {
            top = newNode
            bottom = top
            return
        }

        bottom.next = newNode
        bottom = newNode
    }

    mutating func deQueue() -> T? {

        let topItem: T? = top?.value
        if topItem == nil {
            return nil
        }

        if let nextItem = top.next {
            top = nextItem
        } else {
            top = nil
            bottom = nil
        }

        return topItem
    }

    func isEmpty() -> Bool {

        return top == nil ? true : false
    }

    func peek() -> T? {
        return top?.value
    }
}



// QUEUE NODES TEST

let testAmount = 100

var queueNodes = Queue<Int>()

let queueNodesEnqueStart = NSDate()

for i in 0...testAmount {
    queueNodes.enQueue(i)
}

let queueNodesEnqueEnd = NSDate()

while !queueNodes.isEmpty() {
    queueNodes.deQueue()
}

let queueNodesDequeEnd = NSDate()

// QUEUE ARRAY TEST

var queueArray = QueueArray<Int>()

let queueArrayEnqueStart = NSDate()

for i in 0...testAmount {
    queueArray.enQueue(i)
}

let queueArrayEnqueEnd = NSDate()

while !queueArray.isEmpty() {
    queueArray.deQueue()
}

let queueArrayDequeEnd = NSDate()

// QUEUE NODES RESULT:

print("queueEnqueDuration: \(queueNodesEnqueEnd.timeIntervalSinceDate(queueNodesEnqueStart)), Deque: \(queueNodesDequeEnd.timeIntervalSinceDate(queueNodesEnqueEnd))")

// QUEUE ARRAY RESULT:

print("queueArrayEnqueDuration: \(queueArrayEnqueEnd.timeIntervalSinceDate(queueArrayEnqueStart)), Deque: \(queueArrayDequeEnd.timeIntervalSinceDate(queueArrayEnqueEnd))")

Answer 4

Swift 4个任意类型的简单队列；字符串、整数、数组等

struct Stack<Element>  {
    var items = [Element]()
    mutating func push(_ item: Element) {
        items.append(item)
    }
    mutating func pop() -> Element {
        return items.removeLast()
    }
    mutating func peek() -> Element {
        return items.last!
    }
    mutating func pushFirst(_ item: Element) {
        items.insert(item, at: 0)
    }
}

带有字符串的示例：

 let names = ["Bob", "Sam", "Sue", "Greg", "Brian", "Dave"]

 //create stack of string type
 var stackOfStrings = Stack<String>()

 //add to bottom of stack
 for stringName in names {
    stackOfStrings.push(stringName)
 }

 //print and remove from stack
 for stringName in names {
    print(stringName)
    stackOfStrings.pop(stringName)
 }

 //add to top of stack
 for stringName in names {
    stackOfStrings.pushFirst(stringName)
 }

 //look at item in stack without pop
 for stringName in names {
    //see what Top item is without remove
    let whatIsTopItem = stackOfStrings.peek(stringName)
    if whatIsTopItem == "Bob" {
      print("Best friend Bob is in town!")
    }
 }

 //stack size
 let stackCount = stackOfStrings.items.count

更多信息在这里：

https://developer.apple.com/library/content/documentation/Swift/Conceptual/Swift_Programming_Language/Generics.html

Answer 5

使用数组排队

struct Queue<T> { 
    private var list = [T]() 

    var isEmpty: Bool { return self.list.isEmpty } 
    var front: T? { return self.list.first } 

    mutating func enqueue(_ item: T) { 
        self.list.append(item) 
    } 

    mutating func dequeue() -> T? { 
        guard self.isEmpty == false else { return nil } 
        return self.list.removeFirst() 
    }
}

Swift 语言的队列实现

Queue implementation in Swift language

queue

ios

swift