Javascript is a language most developers either overestimate or underestimate – whatever the case, this is what makes Javascript special. Javascript is a dynamic language, it’s abstract and for this reason also prone to instability. Javascript in the last decade has provided developers with a place for inventiveness and innovation.
Lately I’ve been immersing myself into mathematics, physics, chemistry, philosophy and even linguistics. I found my premise to still hold true – that the universe is at a state of decay, of disorder, and mutation. It’s exactly because of mutation that we are able to manage disorder and chaos, so in a sense we are constantly trying to keep up with ourselves as we simultaneously and inevitably push forward into the future.
Alright this post isn’t really about the natural sciences and the subject of reality. This post is about a fundamental concept in computer science called “Stacks”. However, I have presented in the aforementioned introduction that Javascript provides a dynamic environment for experimentation – instead of setting up a physical lab, I can create a virtual lab so to speak. A virtual lab in which I, the programmer can construct virtual atoms, virtual space time and matter and run formulas against them.
Back to “Stacks”. Stacks have multiple meanings in programming – depending on the context in which one uses it. “Stacks” in lower level programming describe a static memory allocation stored in a computers RAM. In higher level programming, a stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. The best way to illustrate this is through an array object.
How is this related to the natural sciences though? As we shall see the fundamental building blocks that’s used to construct virtual objects (such as an array) is the same building blocks that construct reality. I’ll dedicate an entire post to this once I’ve aggregated my thoughts on math, physics and philosophy.
On to “Stacks”. Let’s use a palindrome to illustrate a basic algorithm. A palindrome is a word that when reversed will spell the same word. Simple enough.
/* Stacks! */
/* functions: push, pop, peek, length */
var letters = [];
var word = "racecar";
var rword = "";
// put letters of word into the stack
for (var i = 0; i < word.length; i++) {
letters.push(word[i]);
}
// pop off the stack in reverse order
for (var i = 0; i < word.length; i++) {
rword += letters.pop();
}
if (rword === word) {
console.log(word + " is a palindrome");
} else {
console.log(word + " is not a palindrome");
}
Arrays
I’m breaking this down line by line since this program is quite short. We are simply initializing an array literal here, the variable or memory here is called “letters”.
var letters = [];
String
Now we want to initialize another variable called “word”, this is the word we want to run through our program – our test subject. The “rword” variable is another string, but an empty one – we can imagine this to be an empty test tube in chemistry.
var word = "racecar"; var rword = "";
Now on to our data structure:
// put letters of word into the stack
for (var i = 0; i < word.length; i++) {
letters.push(word[i]);
}
// pop off the stack in reverse order
for (var i = 0; i < word.length; i++) {
rword += letters.pop();
}
Yeah, there’s a lot going on here – I wasn’t intending on dropping all this in one shot but it was necessary to keep these two operations together. This operation is called a “for loop” and this data structure is used in every programming language, even C, C++ and Java.
In the first “for loop” we are grabbing each letter of “word” and inserting them once by one into the letters array (remember letters = []).
So letters at this point would look like this:
[r, a, c, e, c, a, r]
We’ve manipulate our original array and the aforementioned array is the array we’ll be working with – [r, a, c, e, c, a, r].
To reverse the word now we’ll be using the pop() method to grab the last letter (or element) in the array. Again using the for loop – were going backwards this time using the pop() method.
Concatenation
Using concatenation we construct the “rword” variable – remember that empty test tube? Well were going to attached the letters one by one in reverse fashion.
Finally we can run an if-else statement to check whether the word is a palindrome or not.
if (rword === word) {
console.log(word + " is a palindrome");
} else {
console.log(word + " is not a palindrome");
}
In this case we find that “racecar” is indeed a palindrome – it spells the same both backward and in reverse order. I know what you’re thinking – we could to this by simply looking at it. We’ve created a virtual lab here – and that’s a powerful thing. I’ll let you ponder that a bit, I’m not going to spell everything out. If you’re following along though – stick around for more of my experiments.