jomendez

In JavaScript the Array object is a very powerful data structure with it you can "simulate" other data structures, like Queues, Stacks, List, etc.

There is a list with some of the most important methods of the array object in JavaScript, we going to use them to create/simulate our data structures, you can see example of these methods in action, below.

Array.push(value1, value2, value3,…) – Add one or more Elements to the end of the array. This method will return the new length of it. You can specify multiple comma separated values.
Array.pop() – Removes the last element from an array and returns it.
Array.unshift(value1, value2, value3,…) – Add one or more elements to the beginning of the array. This method will return the new array length. You can specify multiple comma separated values.
Array.shift() – Removes the first element from an array and returns it.
Array.splice(splice(start, deleteCount[, item1[, item2[, ...]]])) - The splice() method changes the content of an array by removing existing elements and/or adding new elements.

Other useful methods.

We are not going to use this methods to create the data structures showed in this post, but it might be handy.

Array.reverse() – Reverses the order by position (the first element becomes the last and the last one becomes the first, etc).

var arr = ['a', 'b', 'c'];
arr.reverse();
console.log(arr); //this will display ["c", "b", "a"]

Array.sort([compareFunction]) – Allows you to sort an array by specifying a compare function which has access to each value in the array you want to sort.

var arr = ['d', 'e', 'b', 'c', 'a'];
arr.sort(function(a, b){
  if (a < b) { return -1; } if (a > b){ return 1; }
  // a must be equal to b
  return 0;
});
console.log(arr); //this will display ["a", "b", "c", "d", "e"]
//Note: for this simple sort you can do arr.sort(), an you'll obtain the same result.

Array.join(separator) – This method takes one or more items in the array and returns a string of values joined by their separator. If you don’t specify a separator, the default is a comma.

var arr = ['a', 'b', 'c'];
var str = arr.join('-');
console.log(str); //this will display "c-b-a"

Array.indexOf(value) – This method allows you to find the first occurrence of the specified value, or –1 if not found.

var arr = ['a', 'b', 'c'];
if(arr.indexOf("a") > -1)
console.log('found "a" in arr');

 

 

 

Data Structures

• Arrays used as Queue

• Arrays used as Stack

• Arrays used as List

 

Arrays as Queue:

A queue follows the First-In First-Out (FIFO) paradigm: the first item added will be the first item removed. An array can be turned into a queue by using the push() and shift() methods. push() inserts the passed argument at the end of the array, and shift() removes and returns the first item, consider the following example:

function Queue(length) {
    var ret = [];

    ret.enqueue = function(a) {
        if(ret.length == length){
             ret.shift();
        }
        return Array.prototype.push.apply(this, arguments);
    };
    ret.dequeue = function(){
        return Array.prototype.shift.apply(this);
    }
    return ret;
}

var aux = Queue(3);
aux.enqueue('cat');
aux.enqueue('dog');
aux.enqueue('duc');
aux.enqueue('worm');
console.log(aux); // should contain dog, duc, worm
aux.dequeue();
console.log(aux);

Arrays used as Stack.

A stack follows the Last-In First-Out (LIFO) paradigm: an item added last will be removed first. The Array class has 2 methods that provide stack functionality. they are push() and pop(). push() appends an item to the end of the array, and pop() removes and returns the last item in the array
push(data) adds data.

pop() removes the most recently added data.

function Stack() {
    var ret = [];

    ret.push = function(a) {
        return Array.prototype.push.apply(this, arguments);
    };
    
    ret.pop = function(){
        return Array.prototype.pop.apply(this);
    }

    return ret;
}

var stack= Stack();
stack.push("A");
stack.push("B");
stack.push("C");
console.log(stack);
stack.pop();
console.log(stack);

Arrays used as List.

A List a collection of unsorted elements, where you can add or remove elements.

function List() {
    var ret = [];
    ret.add = function(element) {
        return Array.prototype.push.apply(this, arguments);
    };
    ret.remove = function(element){
        return Array.prototype.slice.apply(this, ret.splice(ret.indexOf(element), 1));
    }
    return ret;
}

var aux = List();
aux.add('cat');
aux.add('dog');
aux.add('duc');
aux.add('worm');
console.log(aux); 
aux.remove('dog');
console.log(aux);

Wrapping up:

As you can see the those three data structures queue, stack and list are simple arrays wrapped in a function to rename the methods used to add or remove elements from the collections with more semantic names. If you have any enhancement or any subjection please don't hesitate to share with us.

References to learn more:

developer.mozilla.org - Arrays