7월16일 - 자료구조 (Queue, Stack, Hash) with. JavaScript

개요

자료구조를 공부할 때 파이썬이 다루기 쉽다해서 자료구조, 알고리즘은 파이썬으로만 해왔는데

얼마전, 토스 코딩테스트에서 node.js 부문에 대해 문제를 봤을 때 오로지 JavaScript로만 풀 수 있게 되있는걸 볼 수 있었다.

 

문제를 풀 수 있고 없고를 떠나, 앞으로 node.js 관련 개발을 베이스로 깔고 갈텐데

자료구조나 알고리즘을 JavaScript로 다루지 않는다는게 좀 웃긴거 같아서 

당분간은 죽이되든 JavaScript로 연습해볼 생각이다. 

 

Queue

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

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  enqueue(data) {
    const new_node = new Node(data);
    if (this.head === null || this.tail === null) {
      this.head = new_node;
      this.tail = new_node;
      return
    }
    this.tail.next = new_node;
    this.tail = new_node
  }

  dequeue() {
    if (this.head === null) {
      return null;
    }
    const deleted_node = this.head;
    this.head = this.head.next;
    return deleted_node.data;
  }

  peek() {
    if (this.head === null) {
      return null;
    }
    return this.head.data;
  }
}

const queue = new Queue();
queue.enqueue(3);
console.log('peek:', queue.peek());       // peek: 3
queue.enqueue(4);
console.log('peek:', queue.peek());       // peek: 3
queue.enqueue(5);
console.log('peek:', queue.peek());       // peek: 3

console.log('dequeue:', queue.dequeue()); // dequeue: 3
console.log('peek:', queue.peek());       // peek: 4

링크드리스트 사용. head만이 아닌 tail을 써서 삽입하기 쉬운 구조를 만들었다.

링크드리스트를 나열했을 때 왼쪽에 front, 오른쪽에 rear(뒤쪽)이 오게 한다는 이미지를 생각

 

Stack

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

class Stack {
  constructor() {
    this.head = null;
  }

  push(data) {
    const new_node = new Node(data);
    new_node.next = this.head;
    this.head = new_node;
  }

  pop() {
    if (this.head === null) {
      return null;
    }
    const deleted_node = this.head;
    this.head = this.head.next;
    return deleted_node.data;
  }

  peek() {
    if (this.head === null) {
      return null;
    }
    return this.head.data;
  }
}

const stack = new Stack();
stack.push(3);
console.log(stack.peek());  // 3
stack.push(6);
console.log(stack.peek());  // 6
stack.push(9);
console.log(stack.peek());  // 9

console.log(stack.pop());  // 9
console.log(stack.peek());  // 6

마찬가지로 링크드리스트를 사용.

나열했을 때 오른쪽 끝이 bottom인 이미지를 생각

왼쪽인 top에서 push와 pop 모두 이루어지기 때문에 head만 사용한 것을 볼 수 있다. 

 

Hash Table

Chaining X

class Dict {
  constructor() {
    this.items = new Array(8).fill(null);
  }

  #hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash;
  }

  put(key, value) {
    const index = this.#hash(key) % this.items.length;
    this.items[index] = value;
  }

  get(key) {
    const index = this.#hash(key) % this.items.length;
    return this.items[index];
  }
}

const dict = new Dict();
dict.put('test', 3);
console.log(dict.get('test'));

 

Chaining O

class Node {
  constructor(key, value) {
    this.data = [key, value];
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  add(key, value) {
    const new_node = new Node(key, value);
    if (this.head === null) {
      this.head = new_node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = new_node;
    }
  }

  get(key) {
    if (this.head === null) {
      return null;
    } else {
      let current = this.head;
      while (current) {
        const [k, v] = current.data;
        if (key === k) {
          return v;
        } else {
          current = current.next;
        }
      }
      return null;
    }
  }
}

class Dict {
  constructor() {
    this.items = [];
    for (let i = 0; i < 8; i++) {
      this.items.push(new LinkedList());
    }
  }

  #hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash;
  }

  #getIndex(key) {
    return this.#hash(key) % this.items.length;
  }

  put(key, value) {
    const index = this.#getIndex(key);
    this.items[index].add(key, value);
  }

  get(key) {
    const index = this.#getIndex(key);
    return this.items[index].get(key);
  }
}

const dict = new Dict();
dict.put('aa', 111);
dict.put('cc', 222);
dict.put('bbb', 333);
dict.put('dd', 444);
// console.log(dict)

console.log(dict.get('aa'));
console.log(dict.get('cc'));
console.log(dict.get('bbb'));
console.log(dict.get('dd'));

'cc'와 'bbb'의 hash key 값이 같아 위와 같이 세팅

 

중간에 dict를 찍어보면 Node가 박힌 head가 3개밖에 안보이는데

모두 잘 찾는 것을 볼 수 있다. 

'cc'와 'bbb'의 같은 hash key 값이더라도 LinkedList를 통한 chaining 기법을 통해 

중복되는 문제가 발생하지 않은 모습