This is part || of Data Structures & Algorithms using Javascript. I would like to give credit to freeCodeCamp.org for their series of videos covering this topic.
In part I we started off with a simply defining a few data types – an array and a string for storing data in memory. Then we used a “for-loop” to access and manipulate our data structures. Finally we came up with a sequence of steps to test whether a word was a palindrome or not. In part II now, were going to wrap up all that code into what we call a function object.
Functions are a powerful data structure encapsulating your algorithms. Functions also are a good example of “DRY” – Don’t Repeat Yourself.
In software engineering, don’t repeat yourself is a principle of software development aimed at reducing repetition of software patterns, replacing it with abstractions or using data normalization to avoid redundancy.
On to the function itself:
// Creates a Stack
var Stack = function() {
this.count = 0;
this.storage = {};
// Adds a value onto the end of the Stack
this.push = function(value) {
this.storage[this.count] = value;
this.count++;
}
// Removes and returns the value at the end of the stack
this.pop = function() {
if (this.count === 0) {
return undefined;
}
this.count--;
var result = this.storage[this.count];
delete this.storage[this.count];
return result;
}
this.size = function() {
return this.count;
}
// Returns the value at the end of the Stack
this.peek = function(value) {
return this.storage[this.count-1];
}
}
var myStack = new Stack();
myStack.push(1);
myStack.push(2);
console.log(myStack.peek());
console.log(myStack.pop());
console.log(myStack.peek());
console.log("freeCodeCamp");
console.log(myStack.size());
console.log(myStack.peek());
console.log(myStack.pop());
console.log(myStack.peek());
Straight to explaining this algorithm.
Naming an object
If you’re paying close attention – notice we are naming the “Stack” function with a capital “S”. Now, we could have used a lowercased version and just called it “stack” but in the javascript world, we capitalize the word to denote an object we are intending to extend and create from. In old school javascript lingo, this is known as a function constructor. Nowadays we have ECMAScript 6, a huge shift away from using function constructors – instead we use classes, more on this on a later post.
Function variables and scope
We only really have two local variables defined here. In terms of scope, these variables can only be seen by the operations within the scope of the function. The ‘this’ keyword is an important concept in javascript and I’ll admit, this is one of the more difficult concepts for me to understand. The ‘this’ keyword is simply referring to the object itself we defined as “Stack”. So were basically saying something like this.
Stack.count = 0;
Stack.storage = {};
We wouldn’t really do this though so we use ‘this’:
this.count = 0;
this.storage = {};
This is a common pattern in any language – defining your variables, your constants, all the elements that make up a program or an object. For instance of a physics problem, you might want to declare all the elements that make up an atom first – a neutron, a proton, and an electron. And then, if there are any constants measured in time – we can define those as constants. Following these declarations are a sequence of operations we can use to manipulate the data and achieve a desired result.
We have a list of methods we are attaching to the “Stack” object, lets list them down:
this.push(); this.pop(); this.size(); this.peek();
The push method
Breaking it down, we are grabbing the value and simply adding it into our storage object we had declared earlier. We also keep a current count by using the increment operator – “++”
this.storage[this.count] = value; this.count++;
The pop method
The pop method here is a little different compared to the other methods defined in this function constructor. The pop method actually keeps track, or provides a check to see if the current storage object is empty or “0”.
Let’s jot it down again for clarity sake:
this.pop = function() {
if (this.count === 0) {
return undefined;
}
this.count--;
var result = this.storage[this.count];
delete this.storage[this.count];
return result;
}
In the code snippet above we aren’t actually passing any values to the pop method (or function) – we are implementing a sequence of steps here. First we decrement the current count variable by using the “–” operator. From the LIFO concept, we know that we are always referring to the last element in the stack.
Breaking it down even more…
var result = this.storage[this.count];
delete this.storage[this.count];
These two steps here is where the meat of it is – we want to save this.storage[this.count] into the variable first and then delete it. We can then capture the result and return it for inspection and further debugging.
Alright almost done – we’ll cover the last two methods in one shot – the size and peek methods.
this.size = function() {
return this.count;
}
// Returns the value at the end of the Stack
this.peek = function(value) {
return this.storage[this.count-1];
}
The size method is pretty straightforward – we are capturing the current size, or, the number of elements in the storage object.
Finally, the peek method does exactly what it says – we are interested in the last element in the stack, so the peek method allows us to eyeball that last element, if any.
Instantiating an object
In javascript and with most programming languages – the ‘new’ keyword is used to indicate that we are creating a new object.
var myStack = new Stack(); [/javacript] Ok finally... We have a working function constructor, we can start using it! myStack.push(1); myStack.push(2); console.log(myStack.peek()); console.log(myStack.pop());
We are simply adding elements to the storage object – 1 and 2.
We should get the following result when we run our program:
$ node stackfunction.js 2 2
Now that we’ve exercised our programming muscles a bit – we can use this as a fundamental reference point for creating other function constructors. Stay tuned for the next topic – “Sets”. I’m pretty excited.