크래프톤 정글 6기 TIL - Day 8 | 자료구조(스택, 큐, 우선순위 큐)

맨날 편의점 커피 마셨는데, 교육관 근처에도 카페가 있었따!!!

오늘 팀원들과 한솥 도시락 시켜먹구 카페가서 커피 한 잔씩..하였다..구우우욷😊

---

스택

후입선출(LIFO)

Empty	예외 처리 클래스
Full	예외 처리 클래스
__init__	초기화
__len__	데이터 개수
is_empty	스택이 비어있는지 확인
is_full	스택이 가득 차있는지 확인

 

큐

1. 원소의 추가: O(1)

2. 원소의 제거: O(1)

3. 제일 앞/뒤의 원소 확인

4. 제일 앞 뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

- head와 tail은 0번지에서부터 계속해서 증가

- dat[head]~dat[tail-1] :큐의 원소가 들어있는 자리

- 원소수 : tail - head

우선순위 큐

pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐

1. 원소의 추가 O(logN)

2. 우선순위가 가장 높은 원소의 확인 O(1)

3. 우선순위가 가장 높은 원소의 제거 O(logN)

 

Insert

최소 힙: 자식 노드가 부모 노드보다 크지 않음을 만족하는 균형 이진 트리

Fetch

root(루트)예 적힌 값이 최솟값

 

Erase

 

구현