TIL 03 | 자료구조

song hyun·2021년 7월 22일

JavaScript

목록 보기

4/19

자료 구조(Data Structure)

자료 구조는 데이터에 편리하게 접근하고 변경하기

큐(Queue)

이터를 집어넣을 수 있는 선형(linear)자료형 이다.
먼저 집어 넣은 데이터 먼저 나오는 FIFO(First In First Out)구조를 가진다.
데이터를 집어 넣는 enqueue, 데이터를 추출하는 dequeue등의 작업을 할 수 있다.
JavaScript에서는 배열을 이용해서 큐를 구현할 수 있다.

const queue = [];

queue.push(1); // enqueue
queue.push(2); // enqueue

queue.shift(); // dequeue
queue.shift(); // dequeue

스택(Stack)

데이터를 집어넣을 수 있는 선형(linear)자료형 이다.
나중에 집어넣은 데이터가 먼저 나오는 LIFO(List In Frist Qut)를 가진다.
데이터를 집어넣는 push, 데이터를 추출하는 pop, 맨 나중에 집어넣은 데이터를 확인하는 peek등의 작업을 할 수 있다.
JavaScript에서는 배열을 이용해서 큐를 구현할 수 있다.
스택은 서로 관계가 있는 여러 작업을 연달아 수행하면서 이전의 작업 내용을 저장해 둘 필요가 있을 때 널리 사용된다.

const stack = [];

stack.push(1);
stack.push(2);
stack.push(3);

stack[stack.length - 1]; // peek 3
stack.pop(); // 3
stack.pop(); // 2
stack.pop(); // 1

트리(Tree)

트리는 여러 데이터가 계층 구조 안에서 서로 연결된 형태를 나타낼 때 사용한다.

용어

노드(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) - 같은 부모 노드를 갖는 다른 노드를 보고 형제 노드라고 부른다.