In this article, I will briefly explore Stacks and Queues. We will also look at how we can implement these data-structures in Swift, and furthermore we’ll look at the types of applications which we can use stacks and queues for.
As an aside, you will often hear stacks referenced in the context of memory management, this isn’t the topic of this article but you can find out all about Stacks vs Heaps in the context of memory management here, or about memory management in Xcode with ARC here.
The Stack Data Structure
The Stack is a Linear Data Structure and it follows a particular order in which the operations can be performed, as such, a Stack will arrange data into a sequence and it will also have the characteristic of following some kind of defined order in which operations may be performed (Ref#: B). In contrast, a non-linear data structure doesn’t organize the data inside it in a sequential manner (so for example, Trees and Graphs are non-linear) (Ref#: G).
Typically when we talk about a “stack” we’re talking about a structure that gives you LIFO (last-in-first-out) ordering. This means that the last element you add is then the first element you could subsequently remove from the stack.
As we heard above, a stack typically will use a LIFO (last-in-first-out) ordering, meaning that, like the stack of dinner plates in the above image, the most recent item (or plate) added to the stack is also the first to be removed.
Stack Operations
A Stack will use the following operations:
Pop: The pop() operation removes the top item from a stack. (“The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.”)
Push: The push(item) operation adds an item to the top of a stack. Then if this is performed when the stack is full, then this is referred to an Overflow condition.
Peek (or Top): The peek() operation returns the top element of the stack. Because of the design of the stack, we can’t arbitrarily check its contents, that is, with the exception of its topmost element. It’s as if we are looking directly down on a stack of books, we can only see which book is at the top of the pile of books, but can’t tell from that angle what books are under that top-most book on the stack without removing it.
isEmpty: This isEmpty() operation returns true if and only if the stack is empty, otherwise it returns false.
Because of how it is structured, unlike an array, a stack will not provide constant-time access to the ith item, but adding and removing items can still be done in constant time.
Applications of Stacks
A common use case for stacks is in recursive algorithms, this can be where your code is perhaps going through a set of things to do and reaches a point of failure and we then want to backtrack. Stacks have also been used as a way of implementing recursive algorithms iteratively (Ref#: A). Examples of this could include things like the redo and undo features in photo editing software, or the ability to go back and forwards in a web browser perhaps.
Other application of stacks can include:
Balancing of symbols: Specifically when parsing code for opening and closing braces for example. So they are used “to check if the given expression has balanced symbols or not. The algorithm is very much useful in compilers“. The way the compiler might use a stack here is that “Each time parser reads one character at a time. If the character is an opening delimiter like ‘(‘ , ‘{‘ or ‘[‘ then it is PUSHED into the stack. When a closing delimiter is encountered like ‘)’ , ‘}’ or ‘]’ is encountered, the stack is popped. The opening and closing delimiter are then compared. If they match, the parsing of the string continues. If they do not match, the parser indicates that there is an error on the line”(Ref#: J).
We can use Stacks for Infix to Postfix/Prefix conversion, and Algorithms like Tower of Hanoi (illustrated below), Tree Traversals, Stock Span problem, Histogram Problem. There are also things like Backtracking, the Knight Tour Problem, the rat in a maze scenario, the N queen problem, and making a sudoku solver.
In addition, we can use Stacks in Graph Algorithms like Topological Sorting and Strongly Connected Components.
Implementation
There are essentially two ways to implement a stack in code: Using an array, or using a linked list:
Swift Implementation using An Array
Source: Swift algorithm club
Swift Implementation using a Linked List
Source: https://gist.github.com/joshuatbrown/f69cd2a5a0e7308df5c5
The linked list implementation here then is very simple where each Element simply has an optional reference to another Element.
Queues
In contrast to a Stack, a Queue uses FIFO (first-in-first-out) ordering: This means that insertions and deletions happen at different ends of the queue, so “the first item you enqueue is also the first item you dequeue“(Ref#: I).
Queue Operations
Add: add(item) adds an item to the end of a list. This is also called enqueue(element).
Remove: remove() removes the first item from a list. This is also referred to as dequeue().
Peek: peek() returns the top of the queue.
isEmpty: isEmpty() returns true if the queue is empty, otherwise returns false.
Queue in Swift
Implementation Using an Array
Source: Swift Algorithm Club
From the above what we note is of course that we add new elements at the end and dequeue older elements from the front. Or in other words opposite ends. We also note the naming of the functions enqueue and dequeue, and as we are using generics we could create a queue out of a range of different types of objects such as integers (Ints) or String or something else.
Applications of Queues
In the context of iOS development, we can think about the fact that Grand Central Dispatch (GCD) uses Queues. These queues aren’t always simple queues like those described above, but in the case of serial dispatch queues, these will operate in the expected way where operations will be executed in the order in which they were originally added to the dispatch queue.
Other than that, we can definitely use queues for any scenario where we want the first-in-first-out behavior, and this is often useful in scenarios of asynchronous tasks we want to run, but alternatively it could be the case that we might want to do something like queue up a bunch of downloads but then only start downloading them when we are connected to wifi.
Conclusion
We have, in this article, briefly covered what stacks are and how we use them, and what queues are and how we use them. We have seen that what defines them is incredibly simple, yet they can help us solve loads of really interesting problems.
References
A) McDowell, G.L. (2016). Cracking the Coding Interview. CareerCup, Palo Alto, CA.
B) https://www.geeksforgeeks.org/stack-data-structure/
C) https://www.geeksforgeeks.org/stack-data-structure-introduction-program/
D) https://www.raywenderlich.com/800-swift-algorithm-club-swift-stack-data-structure/
E) https://github.com/raywenderlich/swift-algorithm-club/tree/master/Stack
F) https://medium.com/devslopes-blog/swift-data-structures-stack-4f301e4fa0dc
G) https://techdifferences.com/difference-between-linear-and-non-linear-data-structure.html
H) https://www.geeksforgeeks.org/implement-a-stack-using-singly-linked-list/
I) https://github.com/raywenderlich/swift-algorithm-club/tree/master/Queue
J) http://www.studyalgorithms.com/misc/how-can-stacks-be-used-for-checking-balancing-of-symbols/
K) https://www.geeksforgeeks.org/postfix-prefix-conversion/
L) https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues/
Comments