Data structures — Stacks

Stacks are a data structure that store information in the form of a list, allowing only adding and removing elements under a LIFO pattern (last in, first out). In stacks, elements can’t be added or removed out of order, they always have to follow the LIFO pattern.

Some examples of stack usage are:

• JavaScript's call stack.
• Managing function invocations in various programming languages.
• The undo/redo functionality many applications offer.

There’s more than one way to implement a stack, but probably the simplest is using an array with its push and pop methods. If we only use pop and push for adding and deleting elements, we’ll always follow the LIFO pattern and so operating over it like a stack.

Another way is to implement it like a linked list, which may look like this:

class Node {
    constructor(value){
        this.value = value;
        this.next = null;
    }
}
class Stack {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.first){
            this.first = newNode;
            this.last = newNode;
        } else {
            var temp = this.first;
            this.first = newNode;
            this.first.next = temp;
        }
        return ++this.size;
    }
    pop(){
        if(!this.first) return null;
        var temp = this.first;
        if(this.first === this.last){
            this.last = null;
        }
        this.first = this.first.next;
        this.size--;
        return temp.value;
    }
}

The big O of stack methods is the following:

• Insertion — O(1)
• Removal — O(1)
• Searching — O(n)
• Access — O(n)