TIL 자료구조 : 스택,큐,연결리스트,그래프 형태

[공부방향]
1. 각각의 장단점을 파악해야함
2. 내 상황에서 어떤 것이 필요한지 알 수 있어야함

스택 ( Stack )

• Last in, Frist out
• 실생활에서 흔히 볼 수 있음. (ctrl + z, 재귀함수의 call stack 등)
• 가져오기 O(n), 추가 O(1), 삭제 O(1)
  유튜브 [자료구조 알고리즘] 빅오(Big-O)표기법 완전정복

큐 ( Queue)

• First in, First out
• 실생활에서 흔히 볼 수 있음. (자판기, 번호표 등)
• 늦게 추가할수록 순서가 계속 밀린다는 단점을 보완하기위해 우선순위 큐 사용
  (우선순위가 높은 데이터 먼저 사용 ex. 응급실 긴급환자 우선)
• 가져오기 O(n), 추가 O(1), 삭제 O(1)

연결리스트 ( Linked List )

• 실생활 예시 : 플레이 리스트 , 이미지뷰어 등
• 배열과 차이점
  배열: 탐색 / 정렬 용이
  연결리스트 : 추가/ 삭제 용이
• 가져오기 O(n), 추가 O(1), 삭제 O(1)

해시테이블 ( Hash Table )

• 객체 저장구조와 비슷
• 해시함수 : 어떤 값을 넣었을 때, 정보를 암호화 하거나 조금 더 자료를 정리하기 위해 일련의 값으로 만들어 내는 것을 뜻함. (input이 같으면 output은 항상 같다)
• 해시충돌 : 해시함수를 돌린 후 같은 인덱스를 부여받았을 때 일어난다.
• 가져오기 O(1), 추가 O(1), 삭제 O(1)

그래프 형태 자료구조 (그래프, 트리, 이진탐색트리)

그래프 표현 방식

1. 인접리스트(가장 일반적)
   그래프 내 적은 숫자의 간선만을 가지는 경우 용이
   각각의 정점(노드)에 인접한 정점들을 리스트로 표시
   정점 추가, 삭제는 인접리스트가 효율적이다.
   (V= Vertex, 정점, E = Edge , 간선)

• 공간복잡도 : O(V + E)

2. 인접행렬 (정점들을 2차원 배열로 구현)
   간선의 추가와 삭제가 빈번하게 일어나는 경우에는 인접행렬 방식이 효율적이다.

• 공간복잡도 : O(V²)

이진탐색트리(Binary Search Tree)

최대 2개의 자식만 갖는 트리
그 자식노드 역시 2개의 자식만 가짐

• 순회방법

1. 깊이우선탐색(DFS, Depth First Search) : 부모자식 확인후 옆 부모로 넘어감
   1-1.전위순회 : root - left - right
   1-2.중위순회 : left - root - right
   1-3.후위순회: left - right - root
   ( root를 언제 방문하냐 기준으로 나뉘어진다.)

2. 너비우선탐색(BFS, Breadth First Search) : 레벨마다 나열

• 종류

1. 정 이진트리 (Full Binary Tree)
   모든 노드가 0개 || 2개의 자식을 갖는 트리

2. 완전 이진트리 (Complete Binary Tree)
   마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 트리
   (마지막 레벨 자식들은 왼쪽에 몰려있어야 한다.)
   = 힙 (아직 배우지않았다.)

3. 포화 이진트리 (Perfect Binary Tree)
   모든 레벨에서 노드가 꽉 찬 트리

그림참고링크