I'm starting a new serie with this article. Thanks to the today's higher level programming languages we do not need to implement them by ourselves but I believe knowing what they are still gives us great ability to solve some of our day-to-day problems and sometimes they can help us to pass our dream job's interview. Also hey, if you want to build the next big thing you'll definitely need them!
Stack data structure
If you are doing iOS development, you already met with stacks. Navigation controller works like stacks but that may not be a clear example for you. Have you ever move to another house? Think about the books you have and you need to carry them into your new house. You have a small box around as big as your books' can get into. You can't put them side by side, you need to put your books into the box one by one and in a row. I'll put a picture as an example right below.
Think of these books are in the box we mentioned above. If you want to reach the green book, you first need to take the book on the upper side and later another book. This is LIFO mechanism, it stands for Last-In-First-Out. If you understood this example, you already knew how stacks work then. But how can we represent the stacks in code? Let's get in to the action!
There are only two essential operations for stacks:
- push: add an element into the collection
- pop: remove an element from the collection
We could write a stack with classes but I always prefer to use structs if I do not need classes' features like inheritance and etc. Structs are value type and more performant if we compare them with the classes however that could be a whole another blog post. Let's create a generic struct that holds an array of items.
struct Stack<T> {
private var items = [T]()
mutating func push(_ item: T) {
items.append(item)
}
@discardableResult
mutating func pop() -> T? {
items.popLast()
}
}
As you can see from the code above, we created a generic struct that takes whatever type we give. It holds the elements in a generic type of array called items. And you can see the how push and pop methods are implemented. We are using Swift's array methods to understand the stack concepts better but ideally if you study computer science or anything that related to it, your professor is going to want you to implement the array list mechanism by yourself too. Probably in a lower level programming language like C.
Let's also add some helpful utilities for our stack data structure.
var isEmpty: Bool {
items.isEmpty
}
var count: Int {
items.count
}
func peek() -> T? {
items.last
}
So how can we use this structure? Let's look at the examples below to understand that.
var years = Stack<Int>()
years.push(2020)
years.push(2021)
years.push(2022)
print(years.pop())
print(years.pop())
print(years.pop())
var names = Stack<String>()
names.push("Ufuk")
names.push("Canlı")
print(names.pop())
print(names.pop())
If we want to extend the structure that we just created, we could create an initializer so that stack structure can be initialized with a default value instead of empty array of T's. That could be written like the example below. I prefer to use an extension because I want to keep the default initializer too. If you want to add this initializer inside the structure you would lose the default initializer but if you really want to do that, you could override the initializer by adding an empty one.
extension Stack {
init(_ items: [T]) {
self.items = items
}
}
// now we can also initialize our stacks just like this below
var yearsArray = [2020, 2021, 2022]
var years = Stack(yearsArray)
We can still go further with this extension. If we want to use our structure like an ordinary data type and assign values directly at the initialization time we should add this extension.
extension Stack: ExpressibleByArrayLiteral {
init(_ items: T...) {
self.items = items
}
}
// now we can initialize our stacks just like this below
var years: Stack = [2020, 2021, 2022]
One more thing. If want to print out our stack data structure in the console we should add another extension like this below. This is a common approach to achieve this kind of functionality.
extension Stack: CustomStringConvertible {
var description: String {
items.description
}
}
If you enjoy reading this article do not hesitate to share it or make contribution by adding a comment in the comments section below. I will try to continue writing on data structures and algorithms. Thanks for reading!
Cover photo by Juan Gomez on Unsplash