Javascript의 데이터 구조 및 알고리즘... 시작하려면

Javascript에서 공통 데이터 구조 및 알고리즘 구현 중 일부를 함께 컴파일하고 커뮤니티와 공유할 생각이었습니다. 이것은 시리즈의 1부입니다.

이 문서는 DS 및 알고리즘 면접을 준비하는 사람을 위한 시작점으로 작성되었습니다.

1부에서는 다룰 예정입니다.

스택

대기열

이진 검색 트리

병합 정렬 및 이진 검색을 다룹니다.
배열에서 가장 자주 발생하는 항목, 중첩 배열의 요소 합계 및 배열 청크를 찾기 위한 솔루션을 다룹니다.

1. 스택

스택은 LIFO(Last In First Out) 또는 FILO(First In Last Out)를 따르는 선형 데이터 구조입니다. 스택에는 두 가지 주요 작업이 있습니다.

푸시 - 스택 상단에 요소를 추가합니다.

팝 - 가장 최근에 추가된 요소를 제거합니다(스택 맨 위에서).

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
  }
}
class Stack {
  constructor() {
    this.top = null; // no nodes
  }
  push(value) {
    let node = new Node(value);
    node.prev = this.top;
    this.top = node;
  }
  pop() {
    if (this.top) {
      let value = this.top.value;
      this.top = this.top.prev;
      return value;
    } else {
      return 'Stack is empty';
    }
  }
}

let stack1 = new Stack(); // stack to store integers
stack1.push(1);
stack1.push(2);
stack1.push(3);

console.log(stack1.pop()); // 3
console.log(stack1.pop()); // 2
console.log(stack1.pop()); // 1
console.log(stack1.pop()); // stack is empty

2. 대기열

대기열도 선형 데이터 구조입니다. 대기열은 FIFO(First In First Out)를 따릅니다. Queue의 두 가지 주요 작업은 다음과 같습니다.

Enqueue - Queue의 끝에 요소를 추가합니다.

Dequeue - Queue의 헤드에서 요소를 제거합니다.

class Node {
  constructor(val) {
    this.value = val;
    this.next = null;
  }
}
class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  enqueue(val) {
    // to tail
    let node = new Node(val);
    if (!this.head) {
      //if queue is empty, point head and tail to this new node
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node; // make new node as tail
    }
  }
  dequeue() {
    //  from head
    if (this.head) {
      let val = this.head.value;
      this.head = this.head.next;
      return val;
    } else {
      return 'Queue is empty';
    }
  }
}

let q1 = new Queue();

q1.enqueue(1);
q1.enqueue(2);
q1.enqueue(3);

console.log(q1.dequeue()); // 1
console.log(q1.dequeue()); // 2
console.log(q1.dequeue()); // 3
console.log(q1.dequeue()); // Queue is empty

3. 이진 검색 트리

이진 검색 트리는 정렬되거나 정렬된 이진 트리입니다.

루트 노드가 있습니다

.

각 노드(루트 노드 포함)에 노드의 왼쪽 하위 트리에 있는 모든 키보다 크고 오른쪽 하위 트리에 있는 키보다 작은 키가 있습니다

.



삽입

새 노드의 키가 먼저 루트의 키와 비교됩니다.

새 노드의 키가 루트보다 작으면 새 노드를 루트의 왼쪽 자식 키와 비교합니다.

새 노드의 키가 루트보다 크면 새 노드가 루트의 오른쪽 자식과 비교됩니다.

이 프로세스는 새 노드를 리프 노드와 비교한 다음 해당 키에 따라 이 노드의 오른쪽 또는 왼쪽 자식으로 추가할 때까지 계속됩니다. 키가 리프의 키보다 작으면 리프의 왼쪽 자식으로, 그렇지 않으면 리프의 오른쪽 자식으로 삽입됩니다.

순회

3가지 일반적인 이진 트리 순회가 있습니다.

선주문 (노드->왼쪽->오른쪽)

순서대로(왼쪽->노드->오른쪽)

사후 주문(왼쪽->오른쪽->노드)

이진 검색 트리의 순회는 항상 노드 항목의 오름차순 정렬 목록을 생성합니다. 여기에서는 순서 순회를 구현했습니다.

printNode 함수를 재귀적으로 호출하여 왼쪽 하위 트리를 순회합니다.

현재 노드의 키를 인쇄합니다.

printNode 함수를 재귀적으로 호출하여 오른쪽 하위 트리를 순회합니다.

class Node {
  constructor(val) {
    this.value = val;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null; // root node
  }
  insertNode(parentNode, newNode) {
    if (newNode.value < parentNode.value) {
      //check the left child
      parentNode.left !== null
        ? this.insertNode(parentNode.left, newNode)
        : (parentNode.left = newNode);
    } else {
      // check the right child
      parentNode.right !== null
        ? this.insertNode(parentNode.right, newNode)
        : (parentNode.right = newNode);
    }
  }
  insert(val) {
    let newNode = new Node(val);
    this.root !== null
      ? this.insertNode(this.root, newNode)
      : (this.root = newNode);
  }
  printNode(node) {
    if (node.left !== null) {
      this.printNode(node.left); // traverse left subtree
    }
    console.log(node.value);
    if (node.right !== null) {
      this.printNode(node.right); // traverse right subtree
    }
  }
  print() {
    this.root !== null
      ? this.printNode(this.root)
      : console.log('No nodes in the tree');
  }
}

let bst1 = new BinarySearchTree();

bst1.insert(50); 
bst1.insert(30);
bst1.insert(10);
bst1.insert(40);
bst1.insert(20);
bst1.insert(80);
bst1.insert(70);
bst1.insert(60);
bst1.insert(100);
bst1.insert(90);

bst1.print();

도움이 되었기를 바랍니다!

이 시리즈를 확인하는 것을 잊지 마십시오.
곧 추가 예정!!