Stack Data Structure: A First Look
For the majority of people who do not work with computers or in close proximity to computers, the words “data structure” are probably somewhat meaningless, if not at least confusing. Adding the word “stack” in front of those words likely only further obfuscates the problem.
Like in any language, words that do not tangibly relate to something concrete in daily life often tend to mean absolutely nothing to those hearing or reading them. But stack data structure is an extremely important concept to understand and full comprehend, as understanding what it is and how it works can lead to a much greater ability to write clean and fast code, and develop programs and applications that provide elegant solutions for difficult problems.
Let’s begin by quickly reviewing what a data structure is. We will then look at how the stack data structure operates and functions, and some practical applications of it.
A data structure is a way of organizing, managing, and storing information that is important to running businesses, managing financial systems, health records, etc. Put simply, different data structures give us different abilities to work with large quantities (and sometimes not so large) of information (data) that otherwise would become extremely cumbersome, if not impossible to manage and access in a timely manner.
The stack data structure is one of those tools.
Like its title implies, a stack is one-ended in it’s access; or last-in-first-out (LIFO.) What does this mean, you ask?
Just like the image above, a stack of coins, or a stack of pancakes, or a stack of lumber delivered to your property to build a project — that top coin, or that top piece of lumber was the last item put on the stack, and for practical purposes, will be the first item to come off. Attempting to yank the bottom coin out of the stack would result in coins everywhere, and attempting to drag the bottom piece of wood out from underneath a large stack of lumber is an exercise in futility.
Similarly with the stack data structure, whatever piece of information, or data, goes in last, comes out first. Whatever piece of information goes in first, will come out last.
Stack data structures are categorized as linear data types, meaning that each piece of data put in is linked to the piece of data before or after it.
Why does this matter even? To answer this, it would be helpful to understand what problem stacks are best at solving and why understanding the stack data structure can help us become better programmers.
A basic concept of this stack data structure that we are all probably very familiar with is the Command+Z or Command+Y keyboard shortcuts on your computer keyboard. Cmd+Z will undo what you just typed and Cmd+Y will redo what you just undid.
Or to phrase it in stack data structure language — Cmd+Z “pops” your last action from the stack, and Cmd+Y “pushes” it back in.
Although this is not necessarily how Microsoft Word implements their undo command, there is a defined model of this, unsurprisingly referred to as “linear undo.”
Another example of how this is used would be when you look at your file structure on your computer. It likely has a “Recently Used” access area. iTunes also has this feature prominently displayed. The most recently used items are those items that are on the top of the stack.
JavaScript uses a call stack to execute the functions we write. The call stack grows and shrinks as functions are sent to the call stack, executed, and then completed. This is also the reason why JavaScript is referred to as a single-threaded language, and why asynchronous programming is necessary in order to continue workflow uninterrupted.
The stack data structure can also be used effectively to reverse the order of items. Say you insert the numbers 1, 2, and 3 into your stack. The number 3 is now on the top. So when you “pop” the top number off, followed by the next, and the next, you get the reverse order of your original set of numbers: 3, 2, 1.
EXAMPLE OF PUSH() && POP() METHODS
Some languages have this pop and push functionality built right into them. JavaScript has push and pop functions built right into the language, that allow you to use an array as your stack.
For example, if you wanted to reverse a string using JavaScript you could use the stack data structure concept to reverse Johnny Depp’s famous line from “Charlie & The Chocolate Factory,” it would look something like this:
And it’s output would look like this:
This illustrates the last-in-first-out concept iconic of the stack data structure.
PEEK() METHOD
Both the push() and pop() methods are destructive, in that they alter the array being manipulated. There is a third method that can be deployed in order to check what item was last entered into the array. It is aptly named the peek() method. This method does not alter the array at all, but simply provides a “peek” into the array to check the value of the last entered value.
LIMITATIONS
Like any data structure, the stack data structure has its limitations. Every stack is defined a limit, and when it reaches that limit, anything beyond will result in what is called “stack overflow.” This is where the ubiquitous website we all rely on to find solutions to a bug or error originally got its name from.
Conclusion
In conclusion, let’s recap what we have discussed.
The stack data structure is a tool that can be used to perform and achieve specific jobs within the programming environment.
- It follows the last-in-first-out principle, which means that data added to the stack will be removed in the reverse order that it was placed in.
- It has three different methods that can be used to work with and interact with it: the push() method, the pop() method, which both alter the stack, and finally the peek() method, which does not alter the stack, but simply allows the user to check the last item added to the stack.
- Stack data structure is commonly used to undo/redo actions, backtrack through an algorithm, and is used in JavaScript to compile code, which is why JavaScript is referred to as a single-threaded language and requires the use of asynchronous methods to allow it to interact smoothly with browsers.
- Stack data structures are not limitless. Reaching the limit of a stack is referred to as stack overflow.
- Stack data structure is a linear data type, as opposed to a non-linear data type, such as a tree or a graph.
