具有队列和去队列的队列类

Question

我只是在学习“快捷键”，并试图制作一个包含队列和脱队列的队列类。

• 该节点保存每个元素的数据。
• 该队列向“队列”中添加一个元素。
• 删除队列中的第一个元素并返回数据。
• 头和尾是对节点元素的引用，当队列为nil (null)时，节点元素也会指示队列是否为空。

现在，我想知道，我是否正确地做到了这一点，理论和代码都能在Swift (用Java编写代码)中得到改进吗？

class Queue {

    class Node {
        // variables
        var data: String
        var prev: Node?

        init(data: String){
            self.data = data
        }
    }

    // variables
    var head: Node?
    var tail: Node?

    func enqueue(e: String){
        if head == nil && tail == nil {
            head = Node(data: e)
            head?.prev = nil
            tail = head
        } else {
            let temp = Node(data: e)
            tail?.prev = temp
            tail = temp

        }
    }


    func dequeue() -> String{
        let result = head?.data

        if head === tail {
            head = nil
            tail = nil
        } else {
            head = head?.prev
        }
        if (result == nil){
            return "empty"
        }
        return result!
    }

}

测试程序：

var q: Queue
q = Queue()

q.enqueue("One")
q.enqueue("Two")
q.enqueue("Three")

print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())

输出：

一二三空

Answer 1

据我所知，您的代码是正确的。然而，有些东西是可以改进或简化的。

让我们从class Node定义开始：

• 严格地说，data和prev是属性。
• 据我所知，prev是指向在此之后添加的节点的指针，因此我将它称为next。
• 类应该是私有的，因为它不是缩进的，不能在Queue之外使用。
• data应该是一个常量，因为它不会在创建节点后发生变异(属性转到@Feldur，它在注释中注意到了这一点)。
• 次要注意事项:在花括号前应有一个空格。

然后我们有：

private class Node {
    // properties
    let data: String
    var next: Node?

    init(data: String) {
        self.data = data
    }
}

因此，head和tail也是私有属性：

// properties
private var head: Node?
private var tail: Node?

enqueue()方法可以简化。head和tail是否都是nil，所以没有必要同时检查两者。在这里，通过可选绑定检查尾是有意义的，这样如果列表是非空的，或者以其他方式创建的单节点列表，则可以追加一个新节点：

func enqueue(e: String) {
    let node = Node(data: e)
    if let lastNode = tail {
        lastNode.next = node
    } else {
        head = node
    }
    tail = node
}

如果队列为空，则dequeue()方法返回字符串“空”。这是一个“神奇的字符串”，使得不可能将字符串“空”本身存储在队列中。Swift选项就是为了这个目的而做出的:如果队列为空，则该方法应该返回一个可选的String?，即nil。

该方法可以以类似于enqueue()的方式简化。现在，我们通过可选绑定检查初始节点。请注意，不再存在强制展开(!)，通常应该避免这样做：

func dequeue() -> String? {
    if let firstNode = head {
        head = firstNode.next
        if head == nil {
            tail = nil
        }
        return firstNode.data
    } else {
        return nil
    }
}

在测试代码中，队列变量可以在一个语句中定义和初始化：

var q = Queue()

因为dequeue()现在返回一个可选的，所以我们可以在这样的循环中删除元素：

q.enqueue("One")
q.enqueue("Two")
q.enqueue("Three")

while let s = q.dequeue() {
    print(s)
}

最后:在实现中没有什么是字符串特有的。您可以使类成为通用类，以便它也可以与其他数据类型一起使用。只需稍作修改：

• 将Node替换为Node<T> (并将其移出Queue，因为Swift目前不允许泛型类中的嵌套类型)。
• 将Queue替换为Queue<T>。
• 将String替换为T。

然后看起来是这样的：

private class Node<T> {
    let data: T
    var next: Node?

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

class Queue<T> {

    private var head: Node<T>?
    private var tail: Node<T>?

    func enqueue(e: T) {
        let node = Node(data: e)
        if let lastNode = tail {
            lastNode.next = node
        } else {
            head = node
        }
        tail = node
    }

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

测试代码：

var q = Queue<Int>()

q.enqueue(1)
q.enqueue(2)
q.enqueue(3)

while let i = q.dequeue() {
    print(i)
}