4. Stacks

Written by Kelvin Lau

Stacks are everywhere. Here are some common examples of things you would stack:

• pancakes
• books
• paper
• cash

The stack data structure is identical, in concept, to a physical stack of objects. When you add an item to a stack, you place it on top of the stack. When you remove an item from a stack, you always remove the top-most item.

Stack operations

Stacks are useful and also exceedingly simple. The main goal of building a stack is to enforce how you access your data.

There are only two essential operations for a stack:

• push: Adding an element to the top of the stack.
• pop: Removing the top element of the stack.

Limiting the interface to these two operations means that you can only add or remove elements from one side of the data structure. In computer science, a stack is known as a LIFO (last-in-first-out) data structure. Elements that are pushed in last are the first ones to be popped out.

Stacks are used prominently in all disciplines of programming. To list a few:

• iOS uses the navigation stack to push and pop view controllers into and out of view.
• Memory allocation uses stacks at the architectural level. Memory for local variables is also managed using a stack.
• Search and conquer algorithms, such as finding a path out of a maze, use stacks to facilitate backtracking.

Implementation

Open up the starter playground for this chapter. In the Sources folder of your playground, create a file named Stack.swift. Inside the file, write the following:

public struct Stack<Element> {

  private var storage: [Element] = []

  public init() { }
}

extension Stack: CustomDebugStringConvertible {

  public var debugDescription: String {
    """
    ----top----
    \(storage.map { "\($0)" }.reversed().joined(separator: "\n"))
    -----------
    """
  }
}

Here, you’ve defined the backing storage of your Stack. Choosing the right storage type for your stack is important. The array is an obvious choice since it offers constant time insertions and deletions at one end via append and popLast. Usage of these two operations will facilitate the LIFO nature of stacks.

For the fancy chain of function calls in debugDescription, required by the CustomDebugStringConvertible protocol, you are doing three things:

1. Creating an array that maps the elements to String via storage.map { "\($0)" }.
2. Creating a new array that reverses the previous array using reversed().
3. Flattening out the array into a string by using joined(separator:). You separate the elements of the array using the newline character "\n".

This creates a printable representation of Stack types you can use for debugging.

push and pop operations

Add the following two operations to your Stack:

public mutating func push(_ element: Element) {
  storage.append(element)
}

@discardableResult
public mutating func pop() -> Element? {
  storage.popLast()
}

Fairly straightforward! In the playground page, write the following:

example(of: "using a stack") {
  var stack = Stack<Int>()
  stack.push(1)
  stack.push(2)
  stack.push(3)
  stack.push(4)

  print(stack)

  if let poppedElement = stack.pop() {
    assert(4 == poppedElement)
    print("Popped: \(poppedElement)")
  }
}

You should see the following output:

---Example of using a stack---
----top----
4
3
2
1
-----------
Popped: 4

push and pop both have a O(1) time complexity.

Non-essential operations

There are a couple of nice-to-have operations that make a stack easier to use. In Stack.swift, add the following to Stack:

public func peek() -> Element? {
 storage.last
}

public var isEmpty: Bool {
  peek() == nil
}

A stack interface often includes a peek operation. The idea of peek is to look at the top element of the stack without mutating its contents.

Less is more

You may have wondered if you could adopt the Swift collection protocols for the stack. A stack’s purpose is to limit the number of ways to access your data. Adopting protocols such as Collection would go against this goal by exposing all the elements via iterators and the subscript. In this case, less is more!

You might want to take an existing array and convert it to a stack to guarantee the access order. Of course it would be possible to loop through the array elements and push each element.

However, since you can write an initializer that sets the underlying private storage. Add the following to your stack implementation:

public init(_ elements: [Element]) {
  storage = elements
}

Now, add this example to the main playground:

example(of: "initializing a stack from an array") {
  let array = ["A", "B", "C", "D"]
  var stack = Stack(array)
  print(stack)
  stack.pop()
}

This code creates a stack of strings and pops the top element “D.” Notice that the Swift compiler can type infer the element type from the array so you can use Stack instead of the more verbose Stack<String>.

You can go a step further and make your stack initializable from an array literal. Add this to your stack implementation:

extension Stack: ExpressibleByArrayLiteral {
  public init(arrayLiteral elements: Element...) {
    storage = elements
  }
}

Now go back to the main playground page and add:

example(of: "initializing a stack from an array literal") {
  var stack: Stack = [1.0, 2.0, 3.0, 4.0]
  print(stack)
  stack.pop()
}

This creates a stack of Doubles and pops the top value 4.0. Again, type inference saves you from having to type the more verbose Stack<Double>.

Stacks are crucial to problems that search trees and graphs. Imagine finding your way through a maze. Each time you come to a decision point of left, right or straight, you can push all possible decisions onto your stack. When you hit a dead end, simply backtrack by popping from the stack and continuing until you escape or hit another dead end.

Concurrency Checking and Data Race Safety

Swift Concurrency introduces both compiler and runtime safeguards to ensure your code is free from data races. Central to this system is the concept of isolation domains. These are compile-time boundaries that ensure only one task or thread can access mutable state at once. To manage interactions across these boundaries, Swift employs the Sendable protocol. This protocol ensures that instances of conforming types can safely move between isolation domains, preventing accidental data races.

To see why sendability is so useful, open your Swift playground and write the following code:

example(of: "sendability") { @MainActor in // 1.
  // 2.
  let task = Task.detached {
    return Stack([1])
  }
  // 3.
  Task.detached {
    let value = await task.value
    print(value)
  }
}

You’ll immediately get compiler errors, but let’s go over the code before you address those:

1. You’ve made it explicit that this example runs in the MainActor isolation domain.
2. You’ve created a new unstructured, detached Task that returns a new stack.
3. You’ve created another Task and attempt to grab the value returned by the previous task.

Although contrived, the key here is that there are three different concurrency / isolation domains that your stack must be sent between.

Sendability

Before fixing the compiler errors, let’s learn more about Sendable. Sendable is a special marker protocol that, when adopted, tells the compiler that the conforming type can be “sent” to another isolation domain. This is such a useful property that most of the types in the Swift standard library conform to Sendable. This includes not only things like integers and strings, but also collections such as arrays, sets and dictionaries.

There are a few scenarios to think about when conforming to Sendable:

1. Automatic conformance - value types that contain only Sendable data are automatically Sendable within the scope of its own module. The Stack you created is not automatically Sendable since it is compiled in another module that your playground uses.
2. Trivial conformance - value types that contain only Sendable data can be made sendable just by declaring the conformance and letting the compiler do the rest. This is what you will do for your Stack to fix the errors.
3. Classes without mutable state - classes that are marked as final and contain no mutable state can be marked as Sendable. As before, this is as simple as adopting the protocol as there are no protocol requirements. It is impossible for data that is immutable to have race conditions.
4. Classes with mutable state - this case is by far the trickiest. In order for a class with mutable state to conform to Sendable, you’ll need to make sure to protect read/write access. There are many ways to achieve this. For example, you can convert the class to an actor. Alternatively, you can mark the class with a global actor attribute such as @MainActor. Another approach is to use the Mutex type, new in iOS 18, to protect access. If you can’t use Mutex because you need to support older OSes, for example, you can use traditional synchronization strategies like NSLock. Since the compiler can’t reason about these mechanisms, after you do so, you must adopt @unchecked Sendable to tell the compiler to trust you. If you make a mistake here, though, your code is vulnerable to subtle runtime errors and data races.

At the bottom of Stack.swift, write the following:

extension Stack: Sendable where Element: Sendable {}

This protocol extension you created will make Stack Sendable as long as Element is Sendable. Rerun the playground and you will see that the compiler errors go away.

Throughout this book you will build data structures that are used from a single concurrency domain and don’t require sendability. If you plan to use the a data structure across different isolation domains, sendability will make your types more ergonomic in concurrent contexts.

Key points

• A stack is a LIFO, last-in first-out, data structure.
• Despite being so simple, the stack is a key data structure for many problems.
• The only two essential operations for the stack are the push method for adding elements and the pop method for removing elements.
• Making types Sendable makes them transferable to different isolation domains.