Chapter 3. Standing on the Shoulders of Giants

The Swift standard library provides the building blocks by providing basic collection types you can use to build your applications. In this chapter, we're going to build on what we learned in the previous chapter and design several commonly used data structures that are used in computer science. Suppose you're receiving a steady stream of data and you want to ensure that it gets processed in the order it arrived. Well, if you use an array data structure, you would need to ensure the data is appended at the end of the array and read from the beginning of it. What if you needed to insert data based on the priority of the data type?

In this chapter, we're going to learn how to visualize data structures so we'll have a clear picture of what they look like in our head. This will prove helpful when you're working through your application requirements; if you can visualize in your head how the data is stored you'll be able to select the best algorithm...

Iterators, sequences, and collections

The Swift standard library provides several built-in collection types that we looked at back in Chapter 2,  Working with Commonly Used Data Structures. The Swift language runtime provides several language features for working with collections, such as subscripts for shortcuts to access collection elements, and for…in control flow for iterating over collections. By conforming to the built-in protocols, IteratorProtocol, Sequence, and Collection, your custom collection types will gain the same type of access the common language constructs use when using subscript and for…in syntax as native Swift collection types.

Iterators

An iterator is any type that conforms to the IteratorProtocol protocol. The sole purpose of IteratorProtocol is to encapsulate the iteration state of a collection by providing the next() method, which iterates over a collection, returning the next element in a sequence or nil if the end has been reached.

The IteratorProtocol protocol is...

Stack

A stack is a Last In First Out (LIFO) data structure. You can think of a LIFO structure resembling a stack of plates; the last plate added to the stack is the first one removed. A stack is similar to an array but provides a more limited, controlled method of access. Unlike an array, which provides random access to individual elements, a stack implements a restrictive interface that tightly controls how elements of a stack are accessed.

Stack data structure

A stack implements the following three methods:

• push() - Adds an element to the bottom of a stack

• pop() - Removes and returns an element from the top of a stack

• peek() - Returns the top element from the stack, but does not remove it

Common implementations can also include helper operations such as the following:

• count - Returns the number of elements in a stack

• isEmpty() - Returns true if the stack is empty, and false otherwise

• isFull() - If a stack limits the number of elements, this method will return true if it is full and false...

Queue

A queue is a First In First Out (FIFO) data structure. To visualize a FIFO, imagine you're standing in line for the checkout at the grocery store. When the first person (head) in line reaches the cashier, she rings up their purchases, they pay and collect their groceries and leave (pop); the second person in line is now first in line, and we repeat the process.

When a new customer stands (push) in line behind the last person in line, they are now in the tail position.

Queue data structure

A queue implements the following seven operations:

• enqueue() - Adds an element to the back of the queue

• dequeue() - Removes and returns the first element from the queue

• peek() - Returns the first element from the queue, but does not remove it

• clear() - Resets the queue to an empty state

• count - Returns the number of elements in the queue

• isEmpty() - Returns true if the queue is empty, and false otherwise

• isFull() - Returns true if the queue is full, and false otherwise

Common implementations can also...

Circular buffer

A circular buffer is a fixed-size data structure that contains two indices, a head index and a tail index that connects to the beginning of the buffer. When the buffer is full, the head index will loop back to 0. Their main purpose is to accept incoming data until their capacity is full, and then overwrite older elements.

Circular buffers are useful when you need a FIFO data structure. They are similar to the queue data structure, except the tail index wraps to the front of the buffer to form a circular data structure.

Since circular buffers are a fixed size, as they become full the older elements will be overwritten. Because of their fixed size, it is more efficient to use an array data structure internally to store the data instead of a linked list. Generally, once you create a circular buffer, the size will not increase, so the buffer memory size should stay pretty static. An implementation could include the capability to resize the buffer and move the existing elements...

Priority queue

A Priority queue is like a regular queue, except each element has a priority assigned to it. Elements that have a higher priority are dequeued before lower priority elements. Instead of writing my own version of a PriorityQueue for this book, I'm going to reference an implementation by David Kopec. David's Swift PriorityQueue is a popular implementation, and he's done a great job of keep it up to date with all of the frequent Swift language changes. You can find the complete code for PriorityQueue included in this book. I'll also include the GitHub URL to his project at the end of this section.

The PriorityQueue is a pure Swift implementation of a generic priority queue data structure. It features a straightforward interface and can be used with any type that implements Comparable. It utilizes comparisons between elements rather than numeric priorities to determine order. It uses a classic binary heap implementation with O(log n) complexity for pushes (enqueue) and pops (dequeue...

StackList

The last data structure we'll cover in this chapter is the linked list. A linked list is an ordered set of elements where each element contains a link to its successor.

Linked list data structure

Linked lists and arrays are similar; they both contain a set of elements. Arrays are allocated in a contiguous range of memory, whereas linked lists are not. This can be an advantage if you have a large dataset you need to work with but you do not know its size ahead of time. Because linked list nodes are allocated individually, they do not allow random access to the elements they contain. If you need to access the fifth element of a linked list, you need to start at the beginning and follow the next pointer of each node until you reach it. Linked lists do support fast insertion and deletion though, O(1).

There are additional linked list types that are useful for different requirements:

• Doubly linked list - When you want to be able to walk up and down a linked list. Each node contains two...

Summary

In this chapter, we've learned about a few of the common Swift protocols you can implement to provide a consistent and friendly development experience for other developers using your data structures. By conforming to these protocols, other developers will intuitively know how to use common Swift language constructs when working with them.

We then learned how to implement a Stack structure using an array and linked list. We also learned about queues and implemented several types so you can gain experience for choosing the right type based on the requirements for your application.

By this point you should have the confidence and knowledge to extend the data structures we have implemented, as well as be able to implement your own customized versions of them if they do not suit your needs.

In Chapter 4, Sorting Algorithms, we're going to build on the data structures we have implemented in this chapter. We'll learn about sorting algorithms and how to implement them with the various data...