Queue class with enqueue and dequeue

Question

I am just learning swift and tried to make a queue class with enqueue and dequeue.

• The node holds the data for each element
• The enqueue adds an element to the "queue"
• The dequeue deletes the first element in the queue and returns the data
• Head and Tail are references to node elements, which also tells if the queue is empty when they are nil (null)

Now I am wondering, have I done this correctly, both the theory and can the code be improved in Swift (used to code in 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!
 }
}

Testing the program:

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

Output:

One
Two
Three
empty

Answer 1

Your code is correct as far as I can see. However, there are some things which can be improved or simplified.

Let's start with the class Node definition:

• Strictly speaking, data and prev are properties.
• prev is – as I understand it – a pointer to the node that was added after this one, so I would call it next instead.
• The class should be private because it is not indented to be used outside of Queue.
• data should be a constant because it is not mutated after the creation of a node (attributions go to @Feldur who noticed that in a comment).
• Minor note: There should be a space before curly braces.

Then we have:

private class Node {
 // properties
 let data: String
 var next: Node?
 init(data: String) {
 self.data = data
 }
}

Consequently, head and tail are private properties as well:

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

The enqueue() method can be simplified. head and tail are both nil or not, so there is no need to check both. Here it makes sense to check the tail via optional binding, so that a new node can be appended if the list was non-empty, or a single-node list created otherwise:

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

The dequeue() method returns the string "empty" if the queue is empty. This is a "magic string" and makes it impossible to store the string "empty" itself in the queue. Swift optionals were make for this very purpose: The method should return an optional String? which is nil if the queue is empty.

The method can be simplified in a similar manner as enqueue(). Now we check the initial node via optional binding. Note that there is no forced unwrapping (!) anymore, which should generally be avoided:

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

In your test code, the queue variable can be defined and initialized in a single statement:

var q = Queue()

Since dequeue() now returns an optional, we can remove elements in a loop like this:

q.enqueue("One")
q.enqueue("Two")
q.enqueue("Three")
while let s = q.dequeue() {
 print(s)
}

Finally: There is nothing in the implementation which is particular to strings. You can make the class generic so that it can be used with other data types as well. Only minor modifications are necessary:

• Replace Node by Node<T> (and move it outside of Queue, as Swift currently does not allow nested types in generic classes).
• Replace Queue by Queue<T>.
• Replace String by T.

Then it looks like this:

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

Test code:

var q = Queue<Int>()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
while let i = q.dequeue() {
 print(i)
}

• Sigils: Great idea with generic classes, I am still learning Swift and this helped a lot!
• Feldur: 1. Why classes vs structure, which are generally preferred?
• Feldur: 2. Why not make the generic version conform to SewuenceType?
• Feldur: 3. Why are the properties of Node var's when they never need to be mutated?
• Feldur: I appreciate the replies. They make good sense.