데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것
(어떤 데이터의 구체적인 구현 방식은 생략)
널리 사용되는 ADT
큐 (Queue), 스택(Stack), 트리(Tree)
FIFO(First In First Out) : 먼저 집어넣은 데이터가 먼저 나옴
데이터를 집어넣을 수 있는 선형(linear) 자료형
enqueue
: 데이터를 넣음
dequeue
: 데이터를 추출
많이 사용 되는 경우
버퍼(buffer): 순서대로 처리해야 하는 작업을 임시로 저장
JS에서 배열을 이용해서 큐 구현 가능
class Queue {
constructor() {
this._arr = [];
}
enqueue(item) {
this._arr.push(item);
}
dequeue(){
return this._arr.shift();
}
}
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.dequeue(); // 1
LIFO(Last In First Out) : 나중에 집어넣은 데이터가 먼저 나옴
데이터를 집어 넣을 수 있는 선형(linear) 자료형
push
: 데이터를 넣음
pop
: 데이터 추출
peek
: 맨 나중에 집어 넣은 데이터를 확인
스택이 넘칠 때 → 에러 던짐
많이 사용 되는 경우
(서로 관계가 있는 여러 작업을 연달아 수행하면서) 이전의 작업 내용을 저장해 둘 필요가 있을 때
JS에서 배열을 이용해서 스택 구현 가능
class Stack {
constructor() {
this._arr = [];
}
push(item) {
this._arr.push(item);
}
pop() {
return this._arr.pop();
}
peek() {
return this._arr[this._arr.length - 1];
}
}
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop(); // 3
계층 구조 (여러 데이터가 계층 구조 안에서 서로 연결된 형태) 를 나타내기 위해
계층 구조를 통해 알고리즘의 효율을 높이고자 할 때
노드(node
) - 트리 안에 들어있는 각 항목
자식 노드(child node
) - 노드는 여러 자식 노드를 가질 수 있음.
부모 노드(parent node
) - 노드 A가 노드 B를 자식으로 갖고 있다면, 노드 A를 노드 B의 '부모 노드'라고 함.
뿌리 노드(root node
) - 트리의 가장 상층부에 있는 노드
잎 노드(leaf node
) - 자식 노드가 없는 노드
조상 노드(ancestor node
) - 노드 A의 자식을 따라 내려갔을 때 노드 B에 도달할 수 있다면, 노드 A를 노드 B의 조상 노드라고 함.
자손 노드(descendant node
) - 노드 A가 노드 B의 조상 노드일 때, 노드 B를 노드 A의 자손 노드라고 함.
형제 노드(sibling node
) - 같은 부모 노드를 갖는 다른 노드
간단한 형태의
Node
구현 예시
class Node {
constructor(content, children = []) {
this.content = content;
this.children = children;
}
}
const tree = new Node('hello', [
new Node('world'),
new Node('and'),
new Node('fun', [
new Node('javaScript')
]),
])
function traverse(node) {
console.log(node.content);
for(let children of node.children){
traverse(children);
}
}
traverse(tree);
// hello world and fun javascript!
참고