Michael McMillan
Stacks in JavaScript
Practical data structures for practical purposes
In a previous blog post, I discussed why it is important for JavaScript developers to learn how to implement the classic data structures of computer science, such as stacks, lists, queues, and so on. I also talked about how in many cases, the problem being solved will suggest a particular data structure, resulting in an algorithm that almost writes itself. In this post I would like to provide an example of just such a case.
Let’s examine the problem first. We are asked to examine a text and find all the words that are palindromes. A palindrome is a word that is spelled the same forwards and backwards. Some examples of palindromes are “bob” and “racecar.”
Stacks in a Nutshell
The data structure we want to use to solve this problem is a stack. A stack is a list structure where access is only allowed at the top. Think of how you interact with a stack of trays in a cafeteria. If you want to get a tray, you get the tray that is on top; if you want to replace a tray, you place it on the top of the stack. That is how you interact with the data stored in a stack.
Data structures in JavaScript
They're not just for academics
By now, you are aware that JavaScript is no longer a web browser-only programming language. Over the past several years, several server-side JavaScript engines and frameworks have been introduced, including the Mozilla JavaScript shell and, most importantly, Node.js. These systems require that JavaScript programmers learn new techniques for solving problems in ways they could not implement very efficiently or effectively in the browser.
Many years ago, the Swiss computer scientist Niklaus Wirth wrote a book titled Algorithms + Data Structures = Programs. Wirth wrote that a program is formed from a set of algorithms that are based on particular representations and structures of data. Wirth’s formula for writing a computer program is to start with the proper representation and structure of the data, which when followed by a set of algorithms that act to manipulate and transform the data, lead to a successful computer program. A computer program will not be successful if the data structures underlying it are faulty or insufficient.