스택

LIFO (Last In First Out)

큐

FIFO (First In First Out)

→ 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

힙

우선순위 큐를 위해 만들어짐 → 우선순위가 높은 것부터 삭제 (pop)되는 것! → 운영체제 프로세스 스케줄링, 네트워크 트래픽 제어 등에 사용됨

• 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 key(부모 노드) >= key(자식 노드)
• 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 key(부모 노드) <= key(자식 노드)

삽입 → 젤 뒤에 넣고, 부모 노드와 비교하면서 바꾸기

삭제 → 최대값을 삭제하고, 제일 마지막 노드를 가져와서 재구성

그래프 vs 트리

그래프: 단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조

트리: 그래프의 한 종류, 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph). 루트 노드 . 자식 노드는 한개의 부모 노드를 가지고 있음.

• 이진 트리(Binary Tree) : 각 노드가 최대 두 개의 자식을 갖는 트리