The Stack Data Structure
A stack is a type of data structure that puts data in a sequential order, known as a linear data structure. Stacks also follow a Last in, First Out (LIFO) principle where only the last element added to the stack can be accessed.
A good way to imagine this is like putting plates away in a cupboard. We put each plate away one by one and on top of each other and when we want to take a plate we can only take the top one. In technical terms, adding to the stack is called pushing and removing the top element is called popping.
Here is a good diagram showing the stack data structure and how only the top most element can be interacted with.
An important aspect of this structure is the stack frame which is the amount of memory allocated to the stack. In our plate analogy, we can think of this as the size of the cupboard itself; we can only put in as many plates as will fit in the cupboard. Similarly, there is a maximum number of elements that can be pushed onto a stack. If you were to push more than was allowed, a stack overflow error occurs as we have exceeded the allocated memory. This typically happens in endless for/while loops and is the stack’s way of stopping these infinite loops.
One of the most prevalent stack applications is found in expression evaluation. Thinking back to our knowledge of arithmetic expressions, we learned that there was a certain order we needed to consider when evaluating these expressions: Brackets, indices, division, multiplication, addition, and subtraction. Additionally, these expressions are read left to right with arithmetic operators in between the operands.
However, there is another form of arithmetic expression known as the Polish Notation where arithmetic operators are placed before operands as such, only the order which the elements are written is important. For example, instead of A + B, you would write +AB.
We can see how the stack data structure could be used here. Instead of having to worry about the hierarchy of arithmetic operators, we can focus on just the order of the expression.
For example: ( 2 + 3 ) * ( 6 - 1 ) would be written as * + 2 3 - 7 2
Another important application of the stack data structure involves the idea of backtracking. This is where an algorithm may need to revert steps and go backwards in order to get the correct outcome.
The best example of this is in depth-first tree traversal where an algorithm will follow node children to traverse all of the nodes in a tree. Since each leaf node represents a “dead end” in the traversal, algorithms need a way to go backwards to continue traversing the tree.
In this tree diagram, the order in which each node is visited is displayed showing the algorithm backtracking to nodes it has already visited. Stacks can be used here to capture the route we take to traverse the tree. We can see that node 1, 2, 3, and 4 are pushed onto the stack before the algorithm cannot find any more children. It then pops node 4 off of the stack and pushes node 5 on before repeating.
The stack data structure is also used in memory allocation in most modern computer systems. To understand this, we need to know how computers allocate memory and processing power.
Modern computers are multi-threaded meaning there are many threads, each of which have its own individual stack. This means that, even if the stack data structure dictates that we interact only with the top most element at a given time, multiple threads can be working on their own individual processes at the same time. In stack-based memory allocation, each thread is allocated memory known as its stack and the computer system will add processes to this stack.
Thinking from the perspective of the call stack, we can see how it changes when each function is called.
The key takeaways from this topic are:
- It uses the LIFO data structure