## Swift Algorithm Club: Swift Stack Data Structure

Kelvin Lau

The Swift Algorithm Club is an open source project to implement popular algorithms and data structures in Swift, with over 9,000 stars on GitHub.

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.

Note: New to the Swift Algorithm Club? Check out our getting started post first.

## 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.

Note: You’ll implement the internal storage of the stack using an array. This isn’t the most efficient approach, but will do for the purposes of this tutorial.

## 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!

### 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 into 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 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!

Solution Inside: Solution SelectShow

## 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 how the stack is at work. Luckily for you, Swift has a built in protocol called `CustomStringConvertible` that allows you to define how you want print out to the console. 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)```

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

## Generics

Currently, your stack can only store strings. If you wanted to create a stack to store integers, you’ll have to implement a whole new stack geared towards integers. Luckily for you, Swift has your back on this. To start off, update the declaration of your stack to the following:

 ```struct Stack { // ... }```

The pointy brackets declare the struct as generic, allowing the stack to deliver it’s purpose to all types in Swift. Next, find and update all instances of where you wrote “String” and replace it with “Element”. Your `Stack` should look like this:

 ```struct Stack { fileprivate var array: [Element] = []   mutating func push(_ element: Element) { array.append(element) }   mutating func pop() -> Element? { return array.popLast() }   func peek() -> Element? { return array.last } }```

Finally, you’ll have to update the `description` property. There’s just one change to make. Update the following line to match the following:

 ```// previous let stackElements = array.reversed().joined(separator: "\n")   // now let stackElements = array.map { "\(\$0)" }.reversed().joined(separator: "\n")```

The idea here is to transform the elements in the array into `String` before joining them together. Since your stack is now generic, you can’t be sure that the values you’re joining are strings.

Finally, find the line where you initialized your stack and specialize the stack to type `String`:

 `var rwBookStack = Stack()`

Now your stack can be specialized to all types, whether it be `String`, `Int`, or even custom types you create, such as `Person` objects!

## Finishing Touches

There are two other properties that often come with the stack. Often times, you’d like to know whether the stack is empty or not, and how many elements are currently in the stack. Add the following computed properties inside the `Stack`:

 ```var isEmpty: Bool { return array.isEmpty }   var count: Int { return array.count }```

## Where To Go From Here?

I hope you enjoyed this tutorial on making a Stack data structure!

Here is a Swift Playground with the above code. You can also find the original implementation and further discussion in the Stack section of the Swift Algorithm Club repository.

This was just one of the many algorithm clubs focused on the Swift Algorithm Club repository. If you’re interested in more, check out the repo.

It’s in your best interest to know about algorithms and data structures – they’re solutions to many real world problems, and are frequently asked as interview questions. Plus it’s fun!

So stay tuned for many more tutorials from the Swift Algorithm club in the future. In the meantime, if you have any questions on implementing trees in Swift, please join the forum discussion below!

Note: The Swift Algorithm Club is always looking for more contributors. If you’ve got an interesting data structure, algorithm, or even an interview question to share, don’t hesitate to contribute! To learn more about the contribution process, check out our Join the Swift Algorithm Club article.
Kelvin Lau

Kelvin is a physicist turned Swift iOS Developer. He's also one of the two maintainers for the Swift Algorithm Club. While he's currently entrenched with iOS development, he often reminisces of his aspirations to be part of the efforts in space exploration.

Outside of programming work, he's an aspiring entrepreneur and musician. You can find him on his twitter at @KelvinlauKL

... 19 total!

... 16 total!

... 31 total!

... 15 total!

... 11 total!

... 10 total!

... 11 total!

... 11 total!

... 11 total!