Stack(스택)
FILO(First-in-Last-out) / LIFO(Last-in-First-out)
• Push
스택이 다 찼는데 push할 경우 overflow
• Pop
스택이 비어있는 데 pop할 경우 underflow
• size, top
• Push val
if top >= size then overflow
else data[top++] = val
• Pop
if top <= 0 then underflow
else data pop, top--;
Queue(큐)
FIFO(First-in-First-out) / LILO(Last-in-Last-out)
• size, front, rear
• Push val
if rear >= size then overflow
else data[rear++] = val
• Pop
if front >= rear then underflow
else return data[front++]
• Circular queue - 순환하는 큐
• Deque(덱) - 양방향 삽입/삭제 가능
Graph(그래프)
G = (V, E)
• V: 정점
• E: 간선
현실 세계의 많은 구조들을 모델링할 수 있는 틀
• 종류
- 유향 그래프(directed graph)
- 무향 그래프(bi-directed graph / undirected graph)
- 가중치 그래프 등...
• Cycle(싸이클)
- 간선들을 타고 다니다가 자기 자신에게 돌아오는 경로가 존재할 경우
• Connected Graph(연결그래프)
- 모든 정점들이 간선으로 연결된 경우
표현방법
- 인접 행렬 - 2차원 배열 사용
- 단순, 간단, 직관적
- 그래프가 커질수록 매우 비효율적(메모리 낭비)
- 인접 리스트 - vector 사용
- 그래프의 크기가 클 경우 효율적
• vector : 일반적인 배열과 똑같으니 크기가 유동적인 동적 배열
[C++] vector<자료형> 이름;
Tree(트리)
graph의 서브셋 느낌
사이클이 없는 Connected 무방향 그래프
• root
• leaf
트리의 지름
: 트리에서 임의 노드 사이의 거리의 최댓값
종류
• general tree : 일반적인 트리
• binary tree : 모든 노드에 대해 자식의 수가 0, 1, 2
• complete binary tree : leaf를 제외한 모든 노드에 대해 자식 수가 정확히 2인 트리
• AVL tree, Red-Black tree, spanning tree, ...
• binary search tree : 이진 트리의 노드에 값을 할당 -> 서치
힙(Heap)
leaf 노드가 아닌 모든 노드에 대해 부모가 자식보다 높은 우선순위를 가짐. sibling 간에는 우선순위 없음.
트리의 순회 - 전위/중위/후위
- 재귀적으로 구현
