Swift Algorithm Club: Swift Stack Data Structure

Every month, Chris Pilcher, Vincent Ngo, and I feature a cool data structure or algorithm from the club in a tutorial on this site. If your want to learn more about algorithms and data structures, follow along with us!

In this tutorial, you’ll learn how to implement a Swift stack data structure. Stacks are a fundamental data structure that help solve many problems.

This algorithm was first implemented by Matthijs Hollemans, and is now refactored for tutorial format.

Getting Started

Stacks are like arrays, but with limited functionality. You can only push to add a new element to the top of the stack, pop to remove the element from the top, and peek at the top element without popping it off.

Why would you want to do this? Well, in many algorithms, you want to add objects to a temporary list at some point and then pull them off this list again at a later time. Often, the order in which you add and remove these objects matter.

A stack gives you a LIFO or last-in first-out order. The element you pushed last is the first one to come off with the next pop. (A very similar data structure, the queue is FIFO, or first-in first-out.)

A ‘stack’ of RW books. We’ll use this as an example to explain how stacks work.

A ‘stack’ of RW books. We’ll use this as an example to explain how stacks work.

Stack Operations

Stacks have a relatively limited small scope of functionality. Using the stack of books as an example, here’s what a stack should be able to do:

Push

When you want to add an element onto the stack, you push onto the stack. You may think of it as adding a book on top of the stack of books.

Peek

By design, a stack doesn’t allow you to check it’s contents, with the exception of the top element of the stack. A peek method allows you to check what’s on the top of your stack.

You may not check underneath the top of the stack!

You may not check underneath the top of the stack!

Pop

When you want to remove an element in the stack, you pop an element off the stack. You may think of it as removing the top book from the stack of books.

Swift Stack Implementation

Open up a playground to begin implementing your Swift stack!

To start off, write the following into your playground:

struct Stack {
  fileprivate var array: [String] = []
}

Here, you’ve declared a Stack with an array property. You’ll be interacting with the array to implement the push, pop, and peek methods.

Push

Pushing an object onto the stack is relatively straightforward. Add the following method inside the stack:

// 1
mutating func push(_ element: String) {
  // 2
  array.append(element)
}

1. The push method takes a single parameter, an element to add to top of the stack.
2. Notice that a push operation puts the new element at the end of the array, not the beginning. Inserting at the beginning of an array is expensive, an O(n) operation, because it requires all existing array elements to be shifted in memory. Adding at the end is O(1); it always takes the same amount of time, regardless of the size of the array.

Pop

Popping the stack is also straightforward. Add the following method inside the stack, just under the push method:

// 1
mutating func pop() -> String? {
  // 2
  return array.popLast()
}

1. The pop method returns an optional String. The return type is optional to handle the case where the stack is empty in the first place. If you try to pop an empty stack, then you’ll get a nil.
2. The Swift array has a handy method for removing it’s last element. popLast does just that.

Peek

Peeking into the stack is to check the top element of the stack. This should be relatively simple. Swift arrays have a last property that returns it’s last element without mutating itself. Try to do this yourself!

[spoiler title=”Solution”]
Add the following inside the stack:

func peek() -> String? {
  return array.last
}

The peek method is very similar to the pop method. The only difference besides the name is that peek avoids mutating the contents of the array, hence the mutating keyword isn’t necessary in this case.
[/spoiler]

Give it a Whirl!

At this point, your Swift stack is ready for some testing. Write the following at the bottom of your playground:

// 1 
var rwBookStack = Stack()

// 2
rwBookStack.push("3D Games by Tutorials")
// 3
rwBookStack.peek()

// 4
rwBookStack.pop()
// 5
rwBookStack.pop()

On the right panel of your playground, you should see the results of each line:

1. You’ve declared a rwBookStack property and initialized it with a Stack. This needs to be a variable rather than a constant because you need to mutate the stack’s contents.
2. You’ve pushed a string on the stack.
3. Peeking into the stack should yield “3D Games by Tutorials”, the last element you’ve pushed into the stack.
4. Popping the stack should yield “3D Games by Tutorials”, the last element you’ve pushed into the stack.
5. This should yield nil as you’ve popped everything in the stack.

CustomStringConvertible

Currently, it’s quite hard to visualize what elements are in the stack. Luckily for you, Swift has a built in protocol called CustomStringConvertible that allows you to define how you want to represent an object as a string. Write the following just under the Stack implementation (not inside):

// 1
extension Stack: CustomStringConvertible {
  // 2
  var description: String {
    // 3
    let topDivider = "---Stack---\n"
    let bottomDivider = "\n-----------\n"

    // 4
    let stackElements = array.reversed().joined(separator: "\n")
    // 5
    return topDivider + stackElements + bottomDivider
  }
}

This is relatively straightforward:

1. To leverage CustomStringConvertible, you create an extension and adopt the CustomStringConvertible protocol.
2. Implementing description property is what’s required to conform to CustomStringConvertible.
3. For aesthetic design, you’ll use some fab ASCII art in the form of dashes :]. \n is called the newline delimiter, and let’s the system know that you want to create a new line.
4. To show the elements in the stack, you’ll stack up the elements in the array. Since you’ve been appending elements to the back of the array, you’ll need to first reverse the array. After that, the joined(separator:) method simply takes every element in the array and connects them together with a separator in between every element. For example, the array ["3D Games by Tutorials", "tvOS Apprentice"] will become "3D Games by Tutorials\ntvOS Apprentice" after being joined.
5. Finally, you sandwich the stackElements in between the two dividers and return the result as the description for the stack.

Remove the test code from earlier and write the following at the bottom of the playground:

var rwBookStack = Stack()
rwBookStack.push("3D Games by Tutorials")
rwBookStack.push("tvOS Apprentice")
rwBookStack.push("iOS Apprentice")
rwBookStack.push("Swift Apprentice")
print(rwBookStack)

At the bottom of your playgrounds, your console should show the correct representation for your stack:

---Stack---
Swift Apprentice
iOS Apprentice
tvOS Apprentice
3D Games by Tutorials
-----------