Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- flask
- TypeScript
- typeORM
- 게임
- class
- mongoose
- Nest.js
- 자료구조
- dfs
- Express
- GIT
- MongoDB
- game
- Python
- jest
- cookie
- OCR
- 정렬
- Queue
- MySQL
- react
- 공룡게임
- nodejs
- nestjs
- AWS
- JavaScript
- Dinosaur
- Bull
- Sequelize
Archives
- Today
- Total
포시코딩
7월16일 - 자료구조 (Queue, Stack, Hash) with. JavaScript 본문
728x90
개요
자료구조를 공부할 때 파이썬이 다루기 쉽다해서 자료구조, 알고리즘은 파이썬으로만 해왔는데
얼마전, 토스 코딩테스트에서 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 기법을 통해
중복되는 문제가 발생하지 않은 모습
728x90
'TIL' 카테고리의 다른 글
7월18일 - JavaScript의 비동기 작업와 블로킹 (0) | 2023.07.19 |
---|---|
7월17일 - 패키지 매니저 비교 (npm, yarn, yarn-berry, pnpm) (0) | 2023.07.17 |
5월5일 - [Python] PriorityQueue(우선순위 큐), heapq (0) | 2023.05.05 |
5월1일 - [Python] list와 set에서의 데이터 찾기 차이 - 배열과 해시 테이블 (0) | 2023.05.02 |
4월25일 - BFS, 파이썬 범위 만족시키기 & 계산 결과들 활용 (0) | 2023.04.25 |