TIL 03 | 자료구조

자료 구조(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)

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

좋은 웹페이지 즐겨찾기