Hacker School Day 8.Friday: On which I “implemented” a “stack” in JavaScript!

Yes!!!

This afternoon, in a matter of just a few hours, I learned:

  • What is meant by a “stack”: a data structure in which you pile things on top, much like books. These are not meant for accessing data from the earliest elements — they are intended for pushing (adding items to the top) and popping (taking items off the top).
  • What it means to “implement” your own “__________” (in this case a stack): build your own version of the thing, ideally using fewer built-in functions or structures than would be handy. (See below for an example.)
  • What a “linked list” is: (sorta) A data structure in which you store each element and it’s “pointer” to the element before it. This means in order to get from element “a” at the beginning of a stack, to element “f” that you’ve stacked up to now, you’ve got to go from “f” to “e”, then from “e” to “d”, etc., until you get back to “a”. Not sure what situations this would be super-helpful for (same way I feel about a stack), but I guess it’s good if you only need the most recent few elements? (Comments, enlightenment, and such are most welcome!)
  • Node is easy to install with homebrew: literally (first remember to update and doctor your brew):
    ~$ brew update
    ~$ brew doctor
    ~$ brew install node

    DONE! Now I can run js files in the terminal!

On “Implementing” a “Stack”:

Okay, so in JavaScript (as in most higher-level programming languages), there are built-in tools that do the stack-y things you need to do already, so a Super Cheaty Implementation of a stack in JS might be something like this:

function CheatingStack () {
	this.contents = [];
}
CheatingStack.prototype.push = function (item) {
	this.contents.push(item);
};
CheatingStack.prototype.pop = function () {
	return this.contents.pop();
}
CheatingStack.prototype.isEmpty = function () {
	return (this.contents.length === 0);
}

That makes use of built in methods push() and pop(), which put an item on and pop an item off the stack, respectively.

That sort of implementation is neither challenging nor interesting, so naturally I had to try harder. The facilitator, AO, who was helping me with this hinted that soon in SICP (the fundamental book of computer programming that I’m reading), the author will break all data down into pairs, and he showed me how pairs could just be “implemented” in JavaScript as an object with two parameters and two properties. From there, with some on-paper reasoning help from my lovely fellow student RS, I figured it out! I then tested it using console.log(), but I would like to implement more unit-testing methods that AO demonstrated. The trick (for the non-technical readers that I someday hope to have) is to create a tiny “Item” object that merely stores a value and a “pointer” (in this case, the item that comes before it). Then in your stack when you push a new element in, you make a new “item” object for it containing itself as the value and the last head object of your list as what it points to. All you have to track in your “stack” is what object you are currently pointing to. Then when you want to pop an item off the top of your list, you grab that head object, and fetch from inside it the object it’s set to point to and make that your new head. In my initial round of code, I was also storing an extra property called “prev” in my stack, but another facilitator, AK, kindly showed me that was entirely unnecessary! (Another great reason to show someone your code immediately.) For the technically inclined and curious, here’s a link to the code: Implementation of a Stack in JavaScript (gist).

2 thoughts on “Hacker School Day 8.Friday: On which I “implemented” a “stack” in JavaScript!

Leave a Reply

Your email address will not be published. Required fields are marked *