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.
The functions that are traditionally provided in a stack implementation are push(), for placing data onto a stack; pop(), for removing the top element of a stack; peek(), or top(), for displaying the top element of a stack; and length(), or size(), for determining how many elements are on a stack. One of the nice features of the stack is its limited interface. Working with a stack is easy to learn and easy to use because so few operations are allowed.
The reason a stack is the perfect data structure for checking for palindromes is due to the last-in, first-out nature of a stack. By sequentially pushing all the letters of a word onto a stack and then popping them off in the reverse order that they were pushed onto the stack, the new word formed is the exact reverse of the original word. For example, the string “hello” pushed onto and then popped off of a stack leads to the string “olleh.”
JavaScript Arrays Make Stacks Easy
A nice feature of JavaScript is that the Array object already has all the functions we need in order to use an array as a stack. This allows us to avoid the overhead of creating a stack class. Instead, we can just store the letters of a word in an array using the push() function and remove the letters from the array using the pop() function. We can check to make sure we don’t accidentally try to pop off an element from an empty stack by accessing the length property.
Now all we have to do is write the code. Here it is:
var letters = []; // this is our stack
var rword = "";
putstr("Enter a word: ");
var word = readline();
for (var i = 0; i < word.length; i++) {
rword += letters.pop(); // pop off the stack in reverse order
}
if (rword === word) {
print(word + " is a palindrome.");
}
else {
print(word + " is not a palindrome.");
}
Here are a few runs of the program:
Enter a word: bob bob is a palindrome. Enter a word: racecar racecar is a palindrome. Enter a word: hello hello is not a palindrome.
One variation of this program we might want to write is to allow palindromic sentences. For example, the sentence “a man a plan a canal panama” is a palindrome if we squeeze out all the spaces. We can add this ability to our program by looping through the sentence and taking out the spaces, resulting in a “squeezed” word that can then be pushed onto a stack.
Here is the new program:
var letters = [];
var rword = "";
putstr("Enter a sentence: ");
var sentence = readline();
var sword = "";
for (var i = 0; i < sentence.length; i++) {
if (sentence[i] == " ") {
;
}
else {
sword += sentence[i];
}
}
for (var i = 0; i < sword.length; i++) {
letters.push(sword[i]);
}
while (letters.length > 0) {
rword += letters.pop();
}
if (rword === sword) {
print(sentence + " is a palindrome.");
}
else {
print(sentence + " is not a palindrome.");
}
Here are a couple of runs of the new program:
Enter a sentence: a man a plan a canal panama amanaplanacanalpanama is a palindrome. Enter a sentence: now is the time for all good people nowisthetimeforallgoodpeople is not a palindrome.
There are, of course, other ways to write this program that don’t involve using a stack, but there is always more than one way to write any but the simplest of programs. Understanding how stacks work provides the programmer with a blueprint for solving a problem that involves working with data in the reverse order of how it is originally presented. And the stack isn’t the only data structure that provides this advantage. Knowing how to use a wide range of data structures gives a JavaScript programmer a large palette of solutions for many of the problems he or she will face in their day-to-day work.