자료구조 간략 정리

목차

1. 스택(Stack)
2. 큐(Queue)
3. 힙(heap)
4. 트리(Tree)
5. 그래프(Graph)

 

1. 스택(Stack)

스택은 후입선출(LIFO), 즉 마지막에 삽입된 데이터가 가장 먼저 반환되는 자료 구조입니다.

push 연산자로 데이터를 삽입하고, pop 연산자로 가장 나중에 삽입된 데이터를 반환합니다.

2. 큐(Queue)

큐는 선입선출(FIFO), 즉 먼저 삽입된 데이터가 가장 먼저 반환되는 자료구조입니다.

enqueue 연산자로 Back에 데이터를 삽입하고, dequeue 연산자로 front의 가장 먼저 삽입된 데이터를 반환합니다.

 

3. 힙(Heap)

큐에 우선순위 개념을 적용한 자료구조입니다.

데이터들은 각자 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 반환됩니다.

힙의 종류로는 최대 힙, 최소 힙이 있습니다.

 

힙의 특징

1) 완전 이진 트리 구조이다.

2) 여러 데이터들 중, 최대값이나 최솟값을 빠르게 찾을 수 있다.

3) 중복값을 허용한다.

힙의 삽입

최대 힙의 삽입을 예로 들면 아래와 같습니다.

 

1) 가장 마지막에 새로운 데이터를 일단 삽입

2) 새로 삽입된 데이터와 부모 노드의 값을 비교

3) 부모 노드의 값이 더 크면 데이터를 교환

3) 더 크지 않으면 교환을 중단

힙의 삭제

최대 힙의 삭제를 예로 들면 아래와 같습니다.

 

1) 루트 노드를 제거

2) 가장 마지막의 노드를 루트 노드에 삽입

3) 자식 노드의 값이 더 크면 데이터를 교환

4) 더 작으면 교환을 중단

4. 트리(Tree)

트리는 노드와 간선으로 이루어진 자료구조입니다.

 

트리의 특징

1) 트리는 0개 이상의 루트 노드를 가지고, 0개 이상의 자식 노드를 가진다.

2) 노드들은 간선으로 서로 연결되어 있다.

3) 비선형 연결구조로 데이터의 계층적 관계를 표현한다.

4) 그래프의 한 종류로서, 사이클이 없는 연결 그래프이다.

5) 트리의 종류로는 이진 트리, 이진 탐색 트리, 균형 트리, 이진 힙(최대힙, 최소힙) 등이 있다.

5. 그래프(Graph)

그래프는 정점과 간선으로 이루어진 자료구조입니다.

트리도 그래프의 한 종류인데, 트리와는 달리 부모/자식 개념이 없고, 정점마다 간선이 있을 수도 있고 없을 수도 있습니다. 때문에 트리의 계층적 구조와는 달리 네트워크적 구조로 되어 있으며, 정점 간의 관계를 표현하는 데 적합합니다.

대표적으로 지하철 노선도를 예로 들 수 있습니다.

 

그래프의 종류로는 무방향 그래프, 방향 그래프, 가중치 그래프, 완전 그래프가 있습니다.

 

 

 

 

참고 글

- https://gmlwjd9405.github.io/2017/10/01/basic-concepts-of-development-algorithm.html

- https://coding-factory.tistory.com/610