[1] 스택
스택
- Last In First Out 이라는 개념을 가진 선형 자료구조
- 바닥이 막힌 상자를 생각하면 편함
> pop: 요소를 뺌, push: 요소를 넣음
Array로 표현하기
- Stack은 Array로 표현할 수 있음
Linked List로 표현하기
- Stack을 Linked List로 표현할 수 있음
JavaScript에서 사용법
Array로 구현
const stack = [];
// push
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack); // [ 1, 2, 3 ]
// pop
stack.pop();
console.log(stack); // [ 1, 2, 3 ]
// get Top
console.log(stack[stack.length - 1]); // 2Linked List로 구현
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Stack {
constructor() {
this.top = null;
this.size = 0;
}
push(value) {
const code = new Node(value);
node.next = this.top;
this.top = node;
this.size += 1;
}
pop() {
const value = this.top.value;
this.top = this.top.next;
this.size -= 1;
return value;
}
size() {
return this.size;
}
}
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3
stack.push(4);
console.log(stack.pop()); // 4
console.log(stack.pop()); // 2[2] 큐
큐
- First In First Out 이라는 개념을 가진 선형 자료구조
- Linear Queue와 Circular Queue가 존재
- 대기열이라고 생각하면 편함
Linear Queue
Array로 표현하기
Linked List로 표현하기
JavaScript에서 사용법
Array로 구현
const 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;
}
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
console.log(queue.dequeue());
queue.enqueue(8);
console.log(queue.size());
console.log(queue.peek());
console.log(queue.dequeue());
console.log(queue.dequeue());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;
}
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
console.log(queue.dequeue()); // 1
queue.enqueue(8);
console.log(queue.size); // 3
console.log(queue.peek()); // 2
console.log(queue.dequeue()); // 2
console.log(queue.dequeue()); // 4>> Shift함수는 쓰지 마세요!
const queue = [1, 2, 3];
queue.push(4);
const value = queue.shift(); // O(n) !!
console.log(value); // 1Circular Queue
circular queue
- Front와 Rear가 이어져있는 Queue
- Circular Queue는 Linked List로 구현했을 때 이점이 없음
Array로 표현하기
const Queue {
constructor(maxSize) {
this.maxSize = maxSize;
this.queue = [];
this.front = 0;
this.rear = 0;
this.size = 0;
}
enqueue(value) {
if(this.isFull()) {
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;
this.size -= 1;
return value;
}
isFull() {
return this.size === this.maxSize;
}
peek() {
return this.queue[this.front];
}
}
const queue = new Queue(4);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
queue.enqueue(8);
queue.enqueue(16); // Queue is full
console.log(queue.dequeue()); // 1
console.log(queue.dequeue()); // 2
console.log(queue.size()); // 2
console.log(queue.peek()); // 4
queue.enqueue(16);
queue.enqueue(32);
console.log(queue.isFull()); // true[3] 해시 테이블
ex) 사물함
해시 테이블
- 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조
- 삽입은 O(1)이며, 키를 알고있다면 삭제, 탐색도 O(1)로 수행함
해시 함수
- 입력받은 값을 특정 범위 내 숫자로 변경하는 함수
해시 테이블의 문제점
- 해시 함수의 결과가 동일하여 겹친다면? >> 해시 충돌
해시 충돌 (Hash Collision)
1. 선형 탐사법
- 충돌이 발생하면 옆으로 한 칸 이동
- 제곱 탐사법
- 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동
- 이중 해싱
- 충돌이 발생하면 다른 해시 함수를 이용
- 분리 연결법
- 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가
어디에 사용하는가?
Ex) 학생 정보를 어떻게 관리할까?
연결리스트를 사용하면 학생 정보가 알고 싶을 때, O(n)의 시간복잡도가 걸림
배열은 인덱스를 모를 경우 모두 찾아봐야하기 때문에 탐색에 O(n)이 걸림
> 반면, 해시 테이블을 사용하면 O(1)에 찾을 수 있음
> 따라서, 빠르게 값을 찾아야 하는 경우 해시 테이블을 사용하는 것이 좋음
JavaScript에서 사용법
JavaScript Array(배열) = Hash Table - 추천하는 방법x
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"]); // undefinedJavaScript Object(객체) = Hash Table - 가장 간단하고 정석적인 방법
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"]); // undefinedMap
- set 함수를 이용하여 값을 넣고, get함수를 이용하여 값을 찾을 수 있음
- 기본 객체와는 다르게 키값으로 오브젝트나 배열같은 복잡한 타입도 키로 사용 가능
- 객체의 경우 들어오는 값이 정수가 아닌 경우에는 전부 문자열로 바꿔버리기 때문에 다양한 타입을 넣고싶다면 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"); // Map은 Object도, Key로 쓸 수 있음
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"); // key와 Value가 동일하게 들어감
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
안녕하세요