[개념] 자료구조에 뭐가 있는지 알고 코딩을 하자 ♬

자료구조

선형구조

List

연결 리스트

 

Stack

LIFO(Last In First Out)

 

사용 사례

-재귀 알고리즘, 실행취소(뒤로가기), 역순 문자열 만들기 , 후위 표기법 계산

Queue

FIFO(First In First Out)

연산

• add()
• remove()
• peek()
• isEmpty()

사용 사례

-너비 우선 탐색(BFS) 구현, 캐쉬(Cache), 우선순위가 같은 작업예약(인쇄 대기열)

비선형 구조

Tree

이진트리 = 각 노드가 최대 두 개의 자식을 갖는 트리

 

+이진 트리 순회 

중위 순회: 왼쪽 가지 -> 현재노드 -> 오른쪽 가지

전위 순회: 현재노드 -> 왼쪽가지 -> 오른쪽 가지

후위 순회: 왼쪽 가지 -> 오른쪽 가지 -> 현재 노드

 

 

+이진 힙 (최소힙과 최대힙)

• 최소힙(Min Heap)
  • 각 노드의 원소가 자식들의 원소보다 작다. 
• 최대힙(Max Heap)
  • 각 노드의 원소가 자식들의 원소보다 크다.