What… is the Stack?
A Brief Overview of the Stack Data Structure
What is the Stack?
The stack, simply put, is a data structure. That is to say, it’s just a way of organizing and accessing data. Okay, so what’s the deal? What makes it special? The particularity of this data structure is that only the top element is accessible.
Think about a stack of books. The book on top of the stack is readable, but if you want to flip through any other book, you’ll have to remove all the books on top of the one you want first.
The stack data structure works exactly the same way as this hypothetical book stack. (The stack is a stack. Wow.) You can only affect (add, read, or remove) the top element of the stack. This is why the stack order is referred to as Last In, First Out (LIFO).
Simple, right? In theory, yes. But that’s just the top of the stack, so to speak! How does it work? What are the real-world applications? Read on and find out!
What can you do with a stack?
No matter what type of data it contains, there are a finite number of actions you can perform on a stack. The first few are pretty self-evident:
- Initialize an empty stack.
- Determine whether the stack contains any elements (or, conversely, is empty).
- Determine whether the stack is full.
Okay, so we know we can create a stack. We can check to see if it is full. Assuming it isn’t, how do we add some data?
Push & Pop
As we’ve already stated, only the top element of the stack is ever directly accessible. How do we access it? That’s where Push and Pop come in.
To add an element, you Push it to the top of the stack.
To delete an element, you Pop it off the top of the stack.
These are the names given to these actions by convention. They remain consistent no matter what programming language you are using. Don’t ask me why they’re called this though, I don’t make the rules.
Stack Peek
What if we want to access the data at the top of the stack without deleting it? Most languages include some sort of Peek method, which returns the top element of a stack without modifying or deleting it. Though not, strictly speaking, an essential operation, it is very useful and thus frequently implemented alongside Pop.
Why Use Stack?
The stack data structure isn’t new. It’s a concept that’s been around for ages. Early computers used expression evaluation stack to keep track of pending operations while computing higher precedence operations. Let’s look at an example from Philip Koopman’s 1989 publication Stack Computers: the new wave:
X = (A+B)*(C+D)
First, A and B are added together. That value is pushed to the stack while C and D are added, and then retrieved in order to perform the multiplication.
The stack structure is also useful in backtracking procedures, as used in depth-first tree traversal. In order to visit each node on a tree exactly once, you push the location of every node to the stack. When you reach an end-point (a leaf), that location is popped from the stack, letting you (or your program) know which node to visit next.
Call Stack
Another common use for the stack is in the function call and return process. Say function A calls function B, which is defined elsewhere in the code. The return address of function A can be stored at the top of the stack while we travel to function B, execute the code, and then pop out the location to resume the task.
This is the basic functionality of what is known as the Call Stack. In high-level programming languages this action is hidden beneath layers of syntactic abstraction, so the developer is never interacting directly with the call stack. This includes languages such as C++, Python, PHP, and JavaScript.
JavaScript Call Stack Implementation
How does the call stack work in the context of a familiar programming language like JavaScript?
JavaScript, along with many other programming languages, is synchronous and single-threaded. These are complicated concepts to cover in detail. For now, suffice to say that this means that JavaScript can only perform one task at a time, and has to wait until that task is complete before it can start executing the next one.
Which task is executed is determined — you guessed it — by the call stack as described above. I would highly recommend taking a couple minutes to peruse JavaScript Tutorial’s excellent explanation of the call stack in JavaScript.
Stack Overflow
What is stack overflow? It’s more than just a website! As stated above, stacks can become full. Stacks, by definition, have a bounded (predefined) capacity. How big that capacity is is determined by many factors, included the programming language and amount of available memory. When a program tries to push more data than the stack can handle, the stack overflows. Obviously this is bad. It will usually cause your program to crash.
Calling a recursive function without an exit clause will eventually cause stack overflow, no matter how large your stack capacity is:
function badFunction() {
badFunction();
};
badFunction(); //stack overflow
Each subsequent recursive call of badFunction() adds another element to the stack, eventually topping out and causing a stack overflow error.
What’s Next?
This has been a very quick overview of the stack data structure. It is important to grasp these fundamental concepts in order to understand how data is stored and accessed in programming languages and situations that use the stack model. For a more in-depth look into the topic, check out the links below:
More reading
A nice concise explanation of the stack and it’s methods:
Study Tonight: What is Stack Data Structure?
Another explanation of the stack and it’s methods, with coded examples in C++, C, Java, Python, and C#:
Geeks for Geeks: Stack Data Structure
A very high-end explanation of stack from the 80s
Phillip Koopman: Stack Computers: the new wave
A quick, clear overview of the call stack as it is used in JavaScript function calls:
JavaScript Tutorial: JavaScript Call Stack
For more info about tree traversal using stack:
Geeks for Geeks: Inorder Tree Traversal Without Recursion