Abstract data structures JS
Tags: javascript, algorithms
Published: 2020-11-22 19:05:05

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

```javascript
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;
    }
}
```
Example - checking of brackets
```javascript
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;
    }
}
```
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.
```javascript
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;
    }
}
```
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!".
```javascript
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;
    }
}
```
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.
```javascript
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;
    }
}
```
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.
```javascript
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;
    }
}
```
This data structure touch me, people who kill their team will always rule humans who learn data structures.