Swift 语言中的队列实现 [英] Queue implementation in Swift language
问题描述
我正在尝试在 Swift 平台中实现队列集合类型.我遇到了一些关于 peek、poll 和 offer 功能的问题.当我尝试在我的代码中使用这些函数时，它失败了.您对此有什么建议或真正的算法吗?
I m trying to implement Queue collection type in Swift platform. I have got some problems about peek, poll and offer functions. When I try to use these functions in my code, it fails. Do you have any advice or true algorithm for that?
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
}
}
推荐答案
除了错误之外，您可能希望更改一些关于您的实现的事情，以使其更像 Swift.一个是看起来您正在复制 Java 名称，如 poll 和 offer - 这些名称(恕我直言)有点奇怪，部分与需要有两个函数有关，一个异常抛出版本和一个非异常版本.由于 Swift 没有异常，您可能只需使用其他 Swift 集合使用的常规名称来命名它们，例如 append.
Aside from the bugs, there are a couple of things about your implementation that you probably want to change to make it more Swift-like. One is it looks like you're replicating the Java names like poll and offer – these names are (IMHO) a little strange, and partly related to needing to have two functions, an exception-throwing version and a non-exception version. Since Swift doesn't have exceptions, you can probably just name them using the conventional names other Swift collections use, like append.
另一个问题是您的实现将遍历队列合并到队列本身中.最好在集合之外进行这种遍历，而不是将两者混合.Swift 集合使用索引来做到这一点.
The other issue is that your implementation incorporates traversing the queue into the queue itself. It's better to do this kind of traversal outside the collection than mix the two. Swift collections do this with indexes.
这是一个可能的类似 Swift 的队列实现.一、节点和基队列定义:
Here's a possible Swift-like queue implementation. First, the node and base queue definition:
// 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 方法进行扩展:
Then, extend with an append and dequeue method:
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
}
}
}
此时，如果您只想添加和删除，您就差不多完成了.要添加遍历，首先创建一个索引类型，它是对节点类型的简单包装:
At this point, you're almost done if all you want to do is add and remove. To add traversal, first create an index type, which is a simple wrapper on the node type:
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:
Then, use this index to conform to 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)
}
}
从符合集合类型，您可以免费获得一大堆东西:
From conforming to collection type, you get a whole load of stuff for free:
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]
最后，还有 3 种协议需要遵守:ExtensibleCollectionType、Printable 和 ArrayLiteralConvertible:
Finally, there's 3 more protocols that are good to conform to: ExtensibleCollectionType, Printable and 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)) + "]"
}
}
这意味着您现在可以轻松地将队列创建为数组或集合:
These mean you can now create queues as easily arrays or sets:
var q: Queue = [1,2,3]
println(q) // prints [1, 2, 3]
这篇关于Swift 语言中的队列实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
