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
    }
}

- gokhangokce

---

当你说你有“一些问题”和“它失败”时，我认为你应该更加具体。意外的结果、运行时异常…… - Antonio

@Antonio，你说得对。我认为主要问题在于算法。特别是pop和offer算法会返回nil，导致应用程序崩溃。所有这些都是一般性的异常情况，我无法弄清楚。 - gokhangokce

我建议您设置一些断点并花时间进行调试 - 我建议编写一些测试，从非常简单的测试开始（例如测试空队列的长度），逐渐增加其复杂性。 - Antonio

Answer 1

除了存在的缺陷外，你的实现还有两点需要改进以使其更符合Swift风格。 其中一个是看起来你在复制Java名称，比如`poll`和`offer`-这些名称（在我看来）有点奇怪，部分原因是需要有两个函数，一个是抛出异常版本，另一个是非抛出异常版本。由于Swift没有异常处理，你可以使用其他Swift集合通常使用的传统名称，例如append。

另一个问题是你的实现将遍历队列与队列本身合并在一起。最好在集合之外执行此类遍历，而不是混合两者。Swift集合使用索引来完成这种操作。

以下是可能的Swift队列实现。首先，是节点和基本队列定义：

// 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)
    }
}

从符合集合类型开始，您可以免费获得很多东西：

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($0) }  // returns [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]

- Airspeed Velocity

---

非常感谢。这非常有帮助。我正在尝试将我的复杂学术Android项目转换为iOS，但我卡在这里了。因此，我将尝试实现peek、poll和offer功能。再次感谢您。 - gokhangokce

我尝试了你的代码，for循环中出现了分段错误。你有什么建议吗？例如：对于q中的x{}，这会导致分段错误。 - gokhangokce

嗨，Airspeed Velocity， 我目前在我们的Swift 2.3项目中使用此实现，然而，在迁移到Swift 3.0时，ForwardIndexType已重命名为Comparable。您是否可以添加这个Queue实现的Swift 3.0版本？ - chlkdst

使用未声明的类型“Printable” - 有人知道为什么会发生这种情况吗？ - asus

如果有人将它升级到Swift 5+，那就太好了 :) - えるまる

Answer 2

您的模型内部一些细节存在一些问题：

1. 当您首次实例化一个新的 Queue 时，您正在将 head、tail 和 current 初始化为三个不同的 Node 对象（即使还没有排队任何东西！）。这是没有意义的。个人认为，我倾向于将这三个属性设为可选项，并将它们保留为 nil，直到您开始排队为止。

   顺便说一句，当您开始使用这些属性的可选项时，许多其他方法会更简单。

2. 看起来你正试图实现一个双向链表。因此，当您出列时，您需要更新 Queue 属性，但您还需要更新下一个将被出列的项目的 next 指针（因为它仍然将指向您已经出列的那个项目）。您不希望您的链接列表维护对已出列并应该被删除的对象的引用。

3. 当您出列最后一个项目时，确实应该清除 head 和 tail 引用。

4. 您正在实现一个双向链表，而不考虑对象所有权模型。因此，一旦您的列表中有多个项目，您就会在节点之间形成强引用循环，如果不加以纠正，则在队列本身被解除分配时，仍存在对象，则会泄漏。考虑将其中一个引用设为 weak 或 unowned。

5. 我建议您保持简单（只需排队和出列）。在任意链接列表的情况下，poll 和 offer 的概念可能是有意义的，但在队列的上下文中并非如此。 poll 和 offer 的实现也是不正确的（例如，poll 调用 deQueue 来删除尾部，但您返回的对象是 head！），但我假设您只需完全删除这些函数。同样，在队列的上下文中，我不理解 current 的意图。

6. 我建议您使 Queue 和 Node 符合 Printable。它将简化您的调试过程。

- Rob

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))")

- Ryan Huebert

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

- Brian Bird

---

不是回答问题的答案，但却是我在寻找的答案。点赞！ - jboi

如果这是一个队列，那么pop()应该是items.removeFirst()，peek()应该是items.first!。否则你就有一个栈实现。 - peterept

这是正确的，队列是先进先出，而栈是后进先出。下面展示了栈。 - Brian Bird

栈不是队列！如果一个栈具有从前面弹出的功能，那么它可以被用作队列，但很可能没有被有效地编写为这种方式工作。 - Craig B

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() 
    }
}

- kyeahen