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

연결 리스트(Listked List)

JavaScript에는 포인터가 없는 연결 리스트를 자바스크립트에서 객체를 참조하는 방식으로 구현할 수 있다.

그래프(Graph)

그래프 자료 구조 안에 트리자료구조가 포함되어 있고, 트리 안에는 연결 리스트가 포함되어 있다. 즉, 그래프는 주로 인접 행렬, 연결 리스트를 허용한다.