[TIL] JavaScript 주요 문법(4)

Queue

• First In First Out의 개념을 가진 선형 자료구조

Linear Queue

Array

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  
  enqueue(value) {
    this.queue[this.rear++] = value;
  }
  
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }
  
  peek() {
    return this.queue[this.front];
  }
  
  size() {
    return this.rear - this.front;
  }
}

Linked List

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  
  enqueue(newValue) {
    const newNode = new Node(newValue);
    if (this.head === null) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size += 1;
  }
  
  dequeue() {
    const value = this.head.value;
    this.head = this.head.next;
    this.size -= 1;
    return value;
  }
  
  peek() {
    return this.head.value;
  }
}

Circular Queue

class Queue {
  constructor(maxSize) {
    this.maxSize = maxSize;
    this.queue = [];
    this.front = 0;
    this.rear = 0;
    this.size = 0;
  }
  
  enqueue(value) {
    if (this.inFull()) {
      console.log("Queue is Full");
      return;
    }
    this.queue[this.rear] = value;
    this.rear = (this.rear + 1) % this.maxSize;
    this.size -= 1;
  }
  
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front = [this.front + 1] % this.maxSize;
    return value;
  }
  
  isFull() {
    return this.size === this.maxSize;
  }
  
  peek() {
    return this.queue[this.front];
  }
}

---

해시 테이블
키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조

해싱 함수
입력받은 값을 특정 범위 내 숫자로 변경하는 함수

Hash Collision(해쉬 충돌) : 해시 함수의 결과가 동일하여 충돌하는 것

해결법
1. 선형 탐사법 : 충돌이 발생하면 옆으로 한 칸 이동한다.
2. 제곱 탐사법 : 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.
3. 이중 해싱 : 충돌이 발생하면 다른 해시 함수를 이용한다.
4. 분리 연결법 : 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다.

Array

const table = [];
table["key"] = 100;
table["key2"] = "Hello";
console.log(table["key"]); // 100
table["key"] = 349;
console.log(table["key"]); // 349
delete table["key"];
console.log(table["key"]); // undefined

Map

const table = new Map();
table.set("key", 100);
table.set("key2", "Hello");
console.log(table["key"]); //undefined
console.log(table.get("key")); // 100
const object = { a: 1 };
table.set(object, "A1");
console.log(table.get(object)); // A1
table.delete(object);
console.log(table.get(object)); // undefined
console.log(table.keys()); // { 'key, 'key2' }
console.log(table.values()); // { 100, 'Hello' }
table.clear();
console.log(table.values()); // {}

Set

const table = new Set();
table.add("key");
table.add("key2");
console.log(table.has("key")); // true
console.log(table.has("key3")); // false
table.delete("key2");
console.log(table.has("key2")); // false
table.add("key3");
console.log(table.size); // 2
table.clear();
console.log(table.size); // 0

---

그래프

• 정점과 점점 사이를 연결하는 간선으로 이루어진 비선형 자료구조

그래프의 특징

• 정점은 여러 개의 간선을 가질 수 있다.
• 크게 방향 그래프와 무방향 그래프로 나눌 수 있다.
• 간선은 가중치를 가질 수 있다.
• 사이클이 발생할 수 있다.

무방향 그래프

• 간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다.
• 표현하기에 (A, B)와 (B, A)는 같은 간선으로 취급된다.

방향 그래프

• 간선에 방향성이 존재하는 그래프
• 양방향으로 갈 수 있더라도 <A, B>와 <B, A>는 다른 간선으로 취급된다.

연결 그래프

• 모든 정점이 서로 이동 가능한 상태인 그래프

비연결 그래프

• 특정 정점쌍 사이에 간선이 존재하지 않는 그래프

완전 그래프

• 모든 정점끼리 연결된 상태인 그래프

사이클

• 그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분

인접 행렬

const graph = Array.from(Array(5), () => Array(5).fill(false));
graph[0][1] = true; // 0 -> 1
graph[0][3] = true; // 0 -> 3
graph[1][2] = true; // 1 -> 2
graph[2][0] = true; // 2 -> 0
graph[2][4] = true; // 2 -> 4
graph[3][2] = true; // 3 -> 2
graph[4][0] = true; // 4 -> 0

인접 리스트

const graph = Array.from(Array(5), () => []);
graph[0].push(1); // 0 -> 1
graph[0].push(3); // 0 -> 3
graph[1].push(2); // 1 -> 2
graph[2].push(0); // 2 -> 0
graph[2].push(4); // 2 -> 4
graph[3].push(2); // 3 -> 2
graph[4].push(0); // 4 -> 0