Apple Reference, Articles, and Opinions

Data Structures & Algorithms in Swift

Hello and welcome to this series on data structures and algorithms in Swift!

In this series I discuss some of the basics of data structures and algorithms implemented in Swift. I will have a small description of the data structure, a use case for such a data structure, the time complexity for the operations associated with each data structure.

The Stack

Description and Usage

The stack is one of the most simple data structures programmers learn about. It can be visualized as a stack of anything, books, plates, memory addresses, or UIViews. It has last in, first out (LIFO) behavior and you can only “see” one element in the stack. The stack has 3 functions associated with it named push, pop, and top for adding, deleting, and viewing the top element.

Stacks have applications in everything from the View hierarchy in UIKit to add views to the hierarchy, remove views from the hierarchy, and maintain reference to the top most view. Similarly, in the ARM instruction set, stacks are used to store registers and load registers while maintaining a reference via the stack pointer to the top of the stack.

Operations

The view from the programmers perspective is limited to viewing the top most element of the stack. They cannot perform any actions on or view anything else in the data structure. Imagine the programmers view as such:

Programmers View

The first operation we will look at is the push function which allows us to add elements to our data structure. They can only be added to the top part of the stack per the programmers view. The image below illustrates the stack data structure before and after the push operation.

Push View

Below is the Swift code for the push function. This is the only function that takes an argument, the element to be added to our stack. This function returns a boolean value where it’s true if the item was successfully added, false otherwise. We also have a check to see if it exceeds our arbitrary maximum number of elements defined in our data structure.

public func push(_ item: T?) -> Bool {
		if length + 1 == MAXIMUM_NUMBER_OF_ELEMENTS {
			return false
		}
		
		nodes[length] = item
		length += 1
		return true
	}

The second operation is the pop function which removes the top most element of the data structure. Below is an illustration of the stack before and after the pop operation.

Pop View

Below is the Swift code for the pop function in our stack. It returns the element that was just popped from the stack. It first checks to see if there are any elements in the stack to remove.

public func pop() -> T? {
		if length == 0 {
			return nil
		}
		
		length -= 1
		return nodes[length]
	}
	

The last function associated with our data structure is the top function. This function simply gives you a reference to the top of the stack. It does not mutate the data structure. If you assign a variable or constant to this operation you get a copy of the element, unlike the pop operation where you remove the element. View the illustration of the stack before and after the top operation.

Top View

Below is the Swift code for the top function in the stack. Notice that it returns the last element of the array but does not remove it.

public func top() -> T? {
		return nodes[length - 1]
	}

Maintaining a reference to the top is highly important when using this data structure in the ARM assembly language. The stack pointer is the point of reference for loading and saving registers that may need to be called upon in a certain order and losing the stack pointer could be disastrous.

One other cool aspect of stacks is that all three of the operations have constant time complexity O(1) in our implementation.

I have the data structure source code and example program uploaded on my Github if you would like to play around with it. That’s it for this first article on data structures and algorithms in Swift!

Are you in need of help developing your iOS or macOS app? Do you need a custom app built from the ground up for yourself or your business? I am available for hire! Just contact me by sending me an email here or filling out the contact form on my business website

With gratitude,
Jav Solo