The project includes a set of Swift generics queue (FIFO) and stack (FILO) classes to match the functionalities of C++ STL queue and stack classes.
The project implements a set of Swift generics classes • CSingleLinkedListNode: the single linked list node class • CSingleLinkedList: the single linked list • CStack: the stack (FILO) class • CQueue: the queue (FIFO) class
To reach better performance and memory usage, these Swift queue and stack classes are implemented by the set of Swift generics single linked list node and single linked list classes.
The single linked list class, CSingleLinkedList, is the fundamental class for implementation of queue (FIFO) and stack (FILO) classes. It is the wrapper class of single linked list node class, CSingleLinkedListNode, containing the data, reference of next node and a hash value for cycle-finding algorithm implementation
To avoid loop in the CSingleLinkedList class, a cycle-finding algorithm is implemented with a lookup table of CSingleLinkedListNode object’s key with object instance. To ensure the unique key value of each CSingleLinkedListNode object instance in lookup table, the built in integer type hash value property is designed and generated by exponentiation of two random integer variables.
The cycle-finding algorithm is implemented by checking the existence of repeated node object’s key in the look up table, if no finding of repeated key value in look up table, then the linked list is not looped.