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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
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;
}
}
This data structure touch me, people who kill their team will always rule humans who learn data structures.
Top comments (0)