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.