DEV Community

Igor Dubinin
Igor Dubinin

Posted on • Edited on

Abstract data structures JS

Abstract data structures usually not exists in current high level languages. I think about that not like about real structures, but about patterns that help to solve a real issue. In any case i believe these knowledge are helpful in programming and real live.

Stack is abstract data type, the sense is the value that come in last come out first

class Stack{
    constructor() {
        this.array = [];
        this.maxsize = 999;
    }

    push(v) {
        this.array.push(v);
    }

    pop(v) {
        return this.array.pop(v);
    }

    peek() {
        return this.array[this.array.length - 1];
    }

    isEmpty() {
        return ! this.array.length;
    }

    isFull() {
        return this.array.length === this.maxsize;
    }
}
Enter fullscreen mode Exit fullscreen mode

Example - checking of brackets

class BracketsChecker {
    constructor(p) {
        this.string = p.string;
        this.brackets = new Stack();
        this.open = '{[(';
        this.close = '}])';
        this.valid = true;
    }
    check() {
        for(let i = 0; i < this.string.length; i++) {
            if (this.open.indexOf(this.string[i]) > -1) {
                this.brackets.push(this.string[i]);
            } else if (this.close.indexOf(this.string[i]) > -1) {
                if (this.brackets.isEmpty()) {
                    this.valid = false;
                    break;
                }
                const o = this.brackets.pop();
                if (this.open.indexOf(o) !== this.close.indexOf(this.string[i])) {
                    this.valid = false;
                    break;
                }
            }
        }

        if (! this.brackets.isEmpty()) {
            return false;
        }

        return this.valid;
    }
}
Enter fullscreen mode Exit fullscreen mode

This data structure taught me how to check closed brackets.

Deque is abstract data type, here possible to add and remove values from both sides of list.

class Deque {
    constructor() {
        this.array = [];
    }

    isEmpty() {
        return ! this.array.length;
    }
    addRear(v) {
        this.array.push(v);
    }
    addFront(v) {
        this.array.unshift(v);
    }
    removeFront() {
        return this.array.pop();
    }
    removeRear() {
        return this.array.shift();
    }
    size() {
        return this.array.length;
    }
}
Enter fullscreen mode Exit fullscreen mode

Example - palindrome is a phrase, number, or other sequence of characters which reads the same backward as forward, such as madam, racecar, "A fool, a tool, a pool; LOOPALOOTALOOFA!".

class PalindromeChecker {
    constructor(p) {
        this.valid = true;
        this.string = p.string || '';
        this.deque = new Deque();
        for (let i = 0; i < this.string.length; i++) {
            if ([' ', ',', '.', '-', '!', '?', ';', ':'].includes(this.string[i])) {
                continue;
            }
            this.deque.addRear(this.string[i].toLowerCase());
        }
    }
    check() {
        if (this.deque.isEmpty()) {
            return false;
        }
        while (this.deque.size() > 1) {
            const left = this.deque.removeFront();
            const right = this.deque.removeRear();
            if (left !== right) {
                this.valid = false;
                break;
            }
        }

        return this.valid;
    }
}
Enter fullscreen mode Exit fullscreen mode

This data structure taught me what does mean palindrome.

Queue is abstract data type, the sense is the value that come in first come out first.

class Queue {
    constructor() {
        this.array = [];
    }
    enqueue(v) {
        this.array.push(v);
    }
    dequeue() {
        return this.array.shift();
    }
    isEmpty() {
        return ! this.array.length();
    }
    size() {
        return this.array.length;
    }
}
Enter fullscreen mode Exit fullscreen mode

Example - Josephus and his 40 soldiers were trapped in a cave by Roman soldiers. They chose suicide over capture, he and 39 comrades stand in a circle with every seventh man eliminated. Josephus and another man remained until the end and surrendered to the Romans rather than killing themselves.

class JosephusProblem {
    constructor(count, killed) {
        this.k = killed;
        this.array = new Queue();
        for (let i = 0; i < count; i++) {
            this.array.enqueue(i + 1);
        }
    }
    justDoIt() {
        let i = 1;
        while (this.array.size() > 1) {
            const v = this.array.dequeue();
            if (i % this.k) {
                this.array.enqueue(v);
            }
            i++;
        }
        return this.array.array;
    }
}
Enter fullscreen mode Exit fullscreen mode

This data structure touch me, people who kill their team will always rule humans who learn data structures.

Top comments (0)