Swift语言中的队列实现 [英] Queue implementation in Swift language
问题描述
我正在尝试在Swift平台中实现Queue集合类型.我在窥视，民意测验和提供功能方面遇到了一些问题.当我尝试在代码中使用这些功能时，它将失败.您对此有任何建议或正确的算法吗?
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 –这些名称(IMHO)有点奇怪，部分与需要具有两个功能(异常抛出版本和非异常版本)相关.异常版本.由于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方法扩展:
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屋！
