Data Structures in Swift: Queues and Stacks
Two of the more common types of data structures are queues and stacks. Before learning about these data structures I had no idea that I was using them in my code all the time. If you’re not familiar with them yourself, then you probably have to0. Don’t worry, they’re not as scary as they sound.
To backtrack a bit, data structures are simply a way of organizing data. Arrays, sets, and dictionaries are all examples of data structures that store data in one place, however, they each have unique characteristics that differentiates one collection type from another.
Queues are similar to the three collections types mentioned above in that they are used to store a set of data, but are different in that the first item to go into this collection, will be the first item to be removed . This is also known as FIFO, first in first out. You can also think about this as a deli line where the first person to be on line will be the first person to be served.
Below we’ll create our own queue. I’ll be explaining the steps, but I suggest coding along as we go through each one. First, we’ll begin with a struct.
struct Queue<T> {
var list = [T]()
}In our struct we have a property called list that will store all of our data. For the purpose of this example I’ve given each property a generic type.
In this struct we will create two functions: one that enqueues (adds an element into our list), and one that dequeues, (removes elements from our list), like so:
mutating func enqueue(_ element: T) {
list.append(element)
}mutating func dequeue() -> T? {
if !list.isEmpty {
return list.removeFirst()
} else {
return nil
}
}
In our first function we are adding an item into our list, and in our second function, we are checking to see if the list is not empty before we proceed. If there are in fact items in our list, we will remove the first item and return it’s value.
Afterwards we will create a peek function.
func peek() -> T? {
if !list.isEmpty {
return list[0]
} else {
return nil
}
}This function first checks to see if our list is empty, and if it is not, it will show us the first item in our list.
Lastly, we will create computed property that will tell us the status of our list.
var isEmpty: Bool {
return list.isEmpty
}That’s it! You’ve created a queue.
Following our definition, we can see that if we create an instance of a Queue and add items into our object, each element will be placed in the same order they have entered.
var collection = Queue<Int>()collection.enqueue(5)
collection.enqueue(12)// prints: Queue<Int>(list: [5, 8, 12])
Similarly if we were to remove an item from our queue, the first item that was put into our queue will be the first one out.
collection.dequeue()// prints: Queue<Int>(list: [8, 12])
Try it out for yourself and test each function!
Similar to queues, stacks also store data, but they are different in that the order in which we remove each item does not follow the same rules as a queue.
In stacks, we can visualize each item being placed on top of one another — much like how we would create a stack a books. The first item we put into our collection will be at the bottom, or end, of our stack. Like books, if we ever wanted to remove the first book we set down, we would have to remove each book that is on top first. In the case of stacks, the method it follows is LIFO: last in, first out.
Below we’ll create a stack and begin with a struct, just as we did before.
struct Stack<T> {
var array: [T] = []
}In our stack we’ve created a property called array that will store all of our data.
When adding elements to our stack, this is called push, and when we remove an element from our stack, this is called pop. Let’s create a function that will push an item into our array, and pop an item out of our array.
mutating func push(_ element: T) {
array.append(element)
}mutating func pop() -> T? {
if !array.isEmpty {
let index = array.count - 1
let poppedValue = array.remove(at: index) return poppedValue
} else {
return nil
}
}
Our push function adds an item into our array, while our pop function checks to see if our array is not empty. If the array is not empty, we will then remove the last item of our array and return it’s value.
Similar to our queue, we will add a peek function which returns the last item in our array.
func peek() -> T? {
if !array.isEmpty {
return array.last
} else {
return nil
}
}That’s it! You’ve just created a stack.
If you have any questions about these data structures, would like to chat about them, or have another way of implementing them — feel free to reach out!
