gokhangokce gokhangokce - 4 months ago 14
iOS Question

Queue implementation in Swift language

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

Answer

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.

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.

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

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
}

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]

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]
Comments