Implementation of Stack in JavaScript

The Stack data structure is very useful and has many applications. The basic design if that of a linear data structure in which the addition or removal of elements follows the FILO order (first in, last out).

Let’s create a skeleton of a stack class which contains a constructor in which we declare an array to implement our stack.

// Stack class

class Stack {
// We are using an Array to implement our stack
constructor() {
this.items = [];
}
// Functions to be implemented
// push(item)
// pop()
// peek()
// isEmpty()
}

We’ve added some methods on our stack class which we would need to implement, allowing us to add items to the stack (push), take an item off our stack (pop), check the last value of the stack (peek), and check whether the stack is empty (isEmpty).

Let’s add these in.

Push(value) – this adds an element to the stack. The push methods has a parameter which is the value of the item we want to add to the stack.

// push function
push(value) {
// push element into the items
this.items.push(value);
}

Pop() – removes an element from the stack, also returning an error if stack is empty

// pop function
pop() {
// return top most element in the stack
// and removes it from the stack
if(this.items.length == 0) return "Stack is empty";
return this.items.pop();
}

Peek() – returns the top most element in the stack (doesn’t delete it)

// peek function
peek() {
// return the top most element from the stack
// but doesn't delete it
return this.items[this.items.length - 1];
}

isEmpty() – return true if the stack is empty

// isEmpty function
isEmpty() {
// return true if stack is empty
return this.items.length == 0;
}

Let’s run through a quick example of how the we can use our new Stack class.

// Adding element to the stack
stack.push(10);
stack.push(20);
stack.push(30);

// Printing the stack element
// prints [10, 20, 30]
console.log(stack.printStack());

// returns 30
console.log(stack.peek());

// returns 30 and remove it from stack
console.log(stack.pop());

// returns [10, 20]

console.log(stack.printStack());

Prototype inheritance in JavaScript

Every object in JavaScript is linked to a prototype object from which it can inherit properties. All objects created from object literals are linked to object.prototype, an object that comes standard with JavaScript.

When you make a new object, you can select the object that should be its prototype. For example, using the Object.create method, we can specify a bond or invisible link to an existing prototype object.

function createUser(name, score) {
  let newUser = object.create(userFunctionStore)
  newUser.name = name;
  newUser.score = score;
}

let userFunctionStore() {
  increment: function() {this.score++}
}

In the above simplistic example, we are creating a new object newUser, and we are specifying that it should link to the userFunctionStore prototype. Any new user that we create using the createUser function will therefore have a reference to all the functionality in userFunctionStore. The user will have this prototype link stored in it’s _proto_ property.

If we add any new properties to userFunctionStore, those properties will be available immediately to objects that are based off of that prototype.

var user1 = createUser( 'Warren', 8)

It is important to recognise that when we write user1.increment() , increment is not a method on user1, but it’s _proto_ object contains a reference to the userFunctionStore that does contain it. JavaScript will initially try to find the increment method directly on user1, and when it doesn’t find it, it will look in it’s _proto_ object to see if it can find it there.

function userCreator(name, score) {
  this.name = name;
  this.score = score;
{

userCreator.prototype.increment = function(){
  this.score++;
}

let User1 = new userCretaor(‘Eva’, 9);

user1.increment();

In the above example, we are adding functionality to the userCreator function (we can do this because all functions in JavaScript are objects). We store the increment property and function reference in the prototype object of the function.

Using the new keyword automates the above function for us. It will automatically create an empty object named this and will also automatically return this object and save it to the variable name that was declared.

This means under the hood of using the new keyword:

this = object.create(userCreator.prototype)

and at the bottom of the function a hidden:

return this

The above function can be written as:

class user{
	Constructor (name, score){
		this.name = name;
		this.score = score,
	}
increment() {
	this.score++;
	}
}

The constructor will automatically be run when the class is called, and increment will also be stored in the prototype object of the new object.

Any new object created from this class will have a reference in its _proto_ to the object user.protoype. That is to say, user1 or user2’s protoype is user.protoype, or the reference made under user1 and user2’s _proto_ is to the user.prototype object.

A closer look at the forEach() JavaScript array method

Before the Array.forEach() method, iterating through an array in JavaScript would involve using a for loop.

const beans = ['kidney', 'baked', 'black'];

for (let i = 0; i < beans.length; i++) {
  console.log(beans[i]);
}

// kidney
// baked
// black

Using Array.forEach() makes things a bit simpler.

beans.forEach(function(bean) {
  console.log(bean);
}

// kidney
// baked
// black

But what does the Array.forEach() method actually do?

All array methods are functions attached to the Array.prototype object. We want our method to execute a provided function to each element of the array. What would this method look like then? Under-the-hood, the method is still in fact using a for loop.

Array.prototype.forEach = function (callback) {
  if (callback && typeof callback === 'function') {
    for (var i = 0; i < this.length; i++) {
      callback(this[i], i, this);
    }
  }
};

The for loop will iterate through each item in the array, and pass in the current item in the loop, the current index, and the array itself as arguments to the callback provided. Because the method is attached to the prototype, it can use this to refer to the array itself.

Reimplementing the JavaScript Array.push() method

Adding elements to an array is a very common practice when using JavaScript, made easy by the push() method:

const newArray = ['senna', 'prost'];
newArray.push('hill');
// newArray becomes ['senna', 'prost', 'hill']

Let’s try and reimplement a simple version of what the Array.push() method is doing under-the-hood.

In a previous post, we learnt that every JavaScript array has a length property:

newArray.length;  // 3

The Array.length property of an array is the largest integer property name in the array plus one. Remember, the property name refers to the ‘key’ of an element, not the value. The above array is not dissimilar to this object:

const newArray_object = { '0':'senna', '1': 'prost', '2': 'hill'};

We also learnt that we can add an element to the end of array by utilising this length property:

newArray[newArray.length] = 'schumacher';
// newArray becomes ['senna', 'prost', 'hill', 'schumacher']

Given that methods are functions attached to the array prototype object, here is an example of how we could create our our own array object with a push method using our knowledge of the Array.length property:

newArray = {
    length: 0,
    push: function (value) {
        // Place the new value into the
        // next available integer key
        this[this.length] = value;

        // Update the length property
        this.length = this.length + 1;

        // Return the updated length
        return this.length;
    }
};

newArray.push('woods');
newArray.push('mickelson');

newArray[0] //  'woods'
newArray[1] //  'mickleson'
newArray.length  // 2

Arrays in JavaScript

JavaScript’s latest version (ES6) has introduced a number of new Array prototype methods. Over the next few blog posts I’ll go over the most useful of these in detail, including how each of them operate under-the-hood in order to fully understand how they work.

But first off we should understand what an array in JavaScript is. An array in JavaScript is an object. For example, we can create an array using an array literal:

const cricketers = ['amla', 'de villiers', 'smith', 'kohli'];

In our array, the first value will get the property name 0, and the second 1, and so on, allowing us to retrieve value from the array as follows:

cricketers[1];   // 'de villiers'

We can produce a very similar result by creating a new object literal:

const cricketers_object = {
    '0': 'amla',
    '1': 'de villiers',
    '2': 'smith',
    '3': 'kohli',
}

Both cricketers and cricketers_object are objects, and both have exactly the same property names and values. However, cricketers inherits from the Array.prototype, whereas cricketers_object inherits from the Object.prototype.

JavaScript arrays can contain elements of any value type, including nested arrays and objects:

const assortedArray = ['apple', '0.5', ['nested', 'array'], {'name': 'nested'}, true, false, null, undefined];

Array.length

The Array.length of an array is the largest integer property name in the array plus one, for example:

assortedArray.length    // 8

The length property can be set explicitly – setting it to less than the current number will delete those with a property name larger than the new length:

assortedArray.length = 2;
// assortedArray becomes ['apple', '0.5']

We can also append items to the end of an array by using:

assortedArray[assortedArray.length] = 'pineapple';
// assortedArray becomes ['apple', '0.5', 'pineapple']

However, we can rather use Array.push method to append items to the end of an array.

Deleting elements

We can use the delete operator on an array to remove elements, but that leaves a hole in the array, as all elements to the right of the deleted item will retain their property names:

delete assortedArray[0];
// assortedArray becomes [ undefined, '0.5', 'pineapple'

When to use an array instead of object?

There is a simple rule for this: if your property names are small sequential integers, use an array. Otherwise, use an object.

Common Git commands

Working with Git on the command line can be slightly daunting. To help with that, I’ve put together a list of common Git commands, what each one means, and how to use them. I will update this post as I go along!

Git with local repositories

git init

Git init initialises an empty git repository in the directory specified, allowing files within the directory to be added and committed.

git add < file name > # adds specified file to index
git add < subfolder > # adds specified directory to index
git add . # adds all unstaged files to index
git add --all # adds all unstaged files to index

Adds files or directories to the staging area, before they can be committed to the repository.

git commit -m "message"

Records the changes to the local repository. Each commit has a unique id. It is best practice to include a short message that describes the changes for easy reference. Once run, a short description of the changes will show up:

1 file changed, 0 insertions(+), 0 deletions(-)

To combine the add and commit commands, we can use:

git commit -a -m "message"

This will add all tracked files to the staging area and commit them.

git log

will return a log of all the commits in the repository

git status

gives information on the current branch, and lists any untracked changes in the directory.

git branch # lists all branches
git branch < branch name > # creates a new branch
git branch -d < branch name > # deletes a branch

To switch between branches we can use:

git checkout < branch name > # checkout a branch
git checkout -b < new branch name > # create and checkout a new branch

To merge different branches together, we can use git merge. For example, if I have a branch with a new feature on it < newfeature > and I would like to merge it into the < master > branch we can use:

# merge changes from another branch into the current branch
git checkout master
git merge newfeature

Git with remote repositories

To clone a remote repository into our local directory, we can use the following command in the directory we want the repository to reside:

git clone < remote repository name >

By using git clone, git automatically remembers this connection and the remote as ‘origin’. To check this, type:

git remote -v

This will return two lines, the first being the ‘fetch URL’, which is used for reading access, and the second is the ‘Push URL’ which is used for writing access. It most cases, these will be the same.

Warren:main warrenfitzhenry$ git remote -v
origin	< remote repository > (fetch)
origin	< remote repository > (push)

Once connected, we can begin to pull from and push to the remote repository.

The git pull command is used to fetch and download content from a remote repository and immediately update the local repository to match that content. 

git pull origin # updates local branch to the remote
git pull <remote branch name> <local branch name> 

Note that this is a combination of two commands – git fetch and git merge.

git fetch lets you see what the latest state of the remote repository is, without merging those changes locally.

git push < local branch name >

will push a local branch to the remote repository.