JavaScript data structures – Stacks

Stack data structure

A stack is an ordered collection that follows the last in, first out (LIFO) principle. Newly added and to be deleted data are stored on the same end of the stack at the top of the stack, and the other end is at the bottom of the stack. The new element is near the top of the stack, and the old element is near the bottom.

Create a stack

We need to create our own stack, and this stack contains some methods.

• Push (element(s)): Add one (or more) new elements to the top of the stack
• Pop (): deletes the element at the top of the stack and returns it
• Peek (): returns the top element of the stack without doing anything to the stack
• IsEmpty (): checks whether the stack isEmpty
• Size (): returns the number of elements in the stack
• Clear () : empty stack

function Stack() {
    let items = [];
    this.push = function(element) {
        items.push(element);
    };
    this.pop = function() {
        let s = items.pop();
        return s;
    };
    this.peek =  function() {
        return items[items.length - 1];
    };
    this.isEmpty = function() {
        return items.length == 0;  
    };
    this.size = function() {
        return items.length;
    };
    this.clear = function() { items = []; }}Copy the code

However, this approach creates multiple copies of items when creating multiple instances. It’s not very appropriate. How to implement Stack class with ES 6. WeakMap can be used to implement this and ensure that the properties are private.

let Stack = (function() {
        const items = new WeakMap();
        class Stack {
            constructor() {
                items.set(this, []);
            }
            getItems() {
                let s = items.get(this);
                return s;
            }
            push(element) {
                this.getItems().push(element);
            }
            pop() {
                return this.getItems().pop();
            }
            peek() {
                return this.getItems()[this.getItems.length - 1];
            }
            isEmpty() {
                return this.getItems().length == 0;
            }
            size() {
                return this.getItems().length;
            }
            clear() { this.getItems() = []; }}returnStack; }) ();Copy the code

Solve the problem with the stack

The stack can solve the decimal to binary problem, the arbitrary base conversion problem, the balance circle bracket problem, the Hanrota problem.

// Example of decimal to binary problemfunction divideBy2(decNumber) {
    var remStack = new Stack(),
        rem,
        binaryString = ' ';
    while (decNumber > 0) {
        rem = Math.floor(decNumber % 2);
        remStack.push(rem);
        decNumber = Math.floor(decNumber / 2);
    }
    while(! remStack.isEmpty()) { binaryString += remStack.pop().toString(); }returnbinaryString; } // Any base conversion algorithmfunction baseConverter(decNumber, base) {
    var remStack = new Stack(),
        rem,
        binaryString = ' ',
        digits = '0123456789ABCDEF';
    while (decNumber > 0) {
        rem = Math.floor(decNumber % base);
        remStack.push(rem);
        decNumber = Math.floor(decNumber / base);
    }
    while(! remStack.isEmpty()) { binaryString += digits[remStack.pop()].toString(); }return binaryString;
}
Copy the code