Stack implementation using Swift

Question

I would like to request some code review and feedback on a stack implementation using Swift.

Disclaimer: I might have not used protocols, optional unwrapping and error and nil check correctly (still trying to figure out the essence of protocols - but that's the drill I'm going through now).

import Foundation

/* Node conformance */
protocol NodeProtocol {

    typealias IDType;
    typealias IDNode;
    func insertNode(element : IDType, nextNode : IDNode?);
}

/* Stack's conformance prototol */
protocol StackProtocol {

    typealias IDType;
    /* Function to push element on stack */
    func push(element : IDType);
}

class IDNode<IDType> : NodeProtocol
{
    var element: IDType?;
    var nextNode: IDNode?;

    /* Sets the element and updates next pointer */
    func insertNode(element: IDType, nextNode: IDNode?) {

        self.element = element;
        self.nextNode = nextNode;
    }
}

class IDStack<IDType> : StackProtocol
{
    private var stackHead: IDNode<IDType>?;

    init() {

        /* Constructor to initialize the stack */
        stackHead = IDNode<IDType>();
    }

    func push(element: IDType) {

        /* If stackHead is empty - just create a new stack
        * Ideally the constructor should have taken care of this.
        * but in our case - because of optional. stackHead can be NULL.
        * So we don't want to take any chance while pushing element to stack.
        */
        if(stackHead == nil) {
            stackHead = IDNode<IDType>();
        }

        /* if stack's first element is empty - Insert as the first element 
        * At this point stack is guaranteed not NULL. Right? 
        * What if memory allocation fails from above?
        */
        if(stackHead!.element == nil) {
            stackHead!.insertNode(element, nextNode: nil);
        }else {
            /* create a new node and insert the new element at top */
            var nodeToPushInStack: IDNode<IDType>! = IDNode<IDType>();
            /* I'm assuming memory allocation always passes from above.
            * Is it correct?
            */
            nodeToPushInStack.insertNode(element, nextNode: stackHead);
            /* Update stack's head to the new Node */
            stackHead = nodeToPushInStack;
        }

    }

    func popElement() -> IDType? {

        /* Remove from top and return the element. */
        var itemPoppedFromStack : IDType?;

        if(self.stackHead == nil) {
            /* Stack is empty / not initialized */
            return nil;
        }

        itemPoppedFromStack = self.stackHead!.element!;

        if(itemPoppedFromStack == nil) {
            return nil;
        } else {
           /* restore pointer order */
            stackHead = stackHead!.nextNode;
        }
        return itemPoppedFromStack;
    }

    func getLength() -> Double {

        var length: Double = 0;
        var headNode: IDNode<IDType>! = self.stackHead;

        if(headNode == nil) {
            /* stack is probably empty, just return 0 */
            return 0;
        }

        while(self.stackHead != nil) {

            length++;
            self.stackHead = self.stackHead!.nextNode;
        }
        /* restore back stackHead to original head */
        self.stackHead = headNode;

        return length;
    }
}

Answer 1

Let's start with some general remarks:

• Swift does not require semicolons after statements (but they are allowed). From what I have seen since Swift was introduced last year, most people do not write semicolons in Swift.

• Classes are reference types, and the properties of an instance of a class can be modified even if the instance is declares as a constant with let. Therefore you can replace var by let at many places in your code, e.g.

  let nodeToPushInStack: IDNode<IDType>! = IDNode<IDType>()
  

• Often an explicit type annotation is not necessary because the compiler can infer the type of an expression automatically. E.g. the above statement can be shortened to

  let nodeToPushInStack = IDNode<IDType>()
  

Now the "major" points. To simplify things, I'll consider the implementation without protocols first, so in the first part of this answer I'll ignore your protocol definitions and assume that the classes are defined as

class IDNode<IDType> { ... }
class IDStack<IDType> { ... }

First the IDNode class: You have defined element as a variable and optional, but actually node elements are cannot be nil and are never mutated once a node has been been pushed on the stack.

You probably did that because you create "empty" nodes first and then call the insertNode() method to set the element and next pointer. Another reason is that you use nodes "without an element", but I'll come back to that later.

I would suggest to make element a constant and non-optional and replace the insertNode() method by an init method:

class IDNode<IDType> 
{
    let element: IDType
    let nextNode: IDNode?

    init(element : IDType, before: IDNode?) {
        self.element = element
        self.nextNode = before
    }
}

Which leads us to the IDStack class: The push and pop methods are a bit too complicated. The reason is that you use a single node with element == nil for an empty stack, a single node with element != nil for a stack with a single element, and then a linked list of nodes for two or more elements.

It becomes much simpler if you use a linked list with one node for each element in each case, and stackHead points to the front node, or is nil for an empty stack. Then you don't need an init() method because the optional property

private var stackHead: IDNode<IDType>?

is automatically initialized to nil, and pushing an element simplifies to

func push(element: IDType) {
    let newNode = IDNode(element: element, before: stackHead)
    stackHead = newNode
}

Popping an element becomes simpler as well. Note that the preferred way to check an optional (here: stackHead) for nil is optional binding:

func popElement() -> IDType? {
    if let firstNode = stackHead {
        let element = firstNode.element
        stackHead = firstNode.nextNode
        return element
    } else {
        return nil
    }
}

Remark: Your comment

        /* Stack is empty / not initialized */

is misleading: Variables cannot be uninitialized in Swift. This is ensured by the compiler and one of the major design goals in Swift.

Finally your getLength() method: Using Double as return type seems quite strange to me, Int would be appropriate. And I would use a computed property count instead, similar to the count property of Swift's sequence types.

Modifying self.stackHead inside the method temporarily is a bad idea and I can see no reason to do so. Use a local variable instead which traverses through the linked list, and again use optional binding to check if you have hit the end of the list:

var count : Int {
    var numItems = 0
    var currentNode = self.stackHead
    while let node = currentNode {
        numItems++
        currentNode = node.nextNode
    }
    return numItems;
}

---

Back to the protocols: Defining a protocol for "Stack" makes only sense if it contains all required methods:

protocol StackProtocol {

    typealias IDType
    func push(element : IDType)
    func popElement() -> IDType?
    var count : Int { get }
}

Then you can create an instance of IDStack and pass it to a function that expects a StackProtocol. Simple example:

func test<S : StackProtocol where S.IDType == String>(stack : S) {
    stack.push("foo")
    stack.push("bar")
    stack.push("baz")
    print(stack.count)

    while let element = stack.popElement() {
        print(element)
    }
}

test(IDStack<String>())

---

Of course you can also define protocols for both the node and the stack type. Now the node protocol should contain all required properties and methods:

protocol NodeProtocol {
    typealias IDType
    var element : IDType { get }
    var nextNode : Self? { get }
    init(element : IDType, before: Self?)
}

and a concrete implementation would be

final class IDNode<IDType> : NodeProtocol
{
    let element: IDType
    let nextNode: IDNode?

    init(element : IDType, before: IDNode?) {
        self.element = element
        self.nextNode = before
    }
}

(Please don't ask me why the final is necessary here :)

To make the stack independent of the used node class, the stack protocol uses node protocol as generic placeholder (and not IDType as you did):

protocol StackProtocol {

    typealias NodeType : NodeProtocol
    func push(element : NodeType.IDType)
    func popElement() -> NodeType.IDType?
    var count : Int { get }
}

and a concrete implementation (in terms of a generic node type) is

class IDStack<Node : NodeProtocol> : StackProtocol
{
    typealias NodeType = Node
    private var stackHead: Node?

    func push(element: Node.IDType) {
        let newNode = Node(element: element, before: stackHead)
        stackHead = newNode
    }

    func popElement() -> Node.IDType? {
        if let firstNode = stackHead {
            let element = firstNode.element
            stackHead = firstNode.nextNode
            return element
        } else {
            return nil
        }
    }

    var count : Int {
        var numItems = 0
        var currentNode = self.stackHead
        while let node = currentNode {
            numItems++
            currentNode = node.nextNode
        }
        return numItems;
    }
}

As an example, a stack of strings could now be created with

let stack = IDStack<IDNode<String>>()