자료구조(3) 스택, 큐 & Set, Map

스택

• 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO)을 가진 자료 구조
• 삽입(push) 삭제(pop) O(1) , 탐색 O(n)이 소요
• 재귀함수, 깊이우선탐색(DFS) , 웹브라우저 방문 기록 등에 쓰임

큐

• 먼저 집어 넣은 데이터가 먼저 나오는 성질(FIFO)을 지닌 자료 구조
• 삽입(enque) 삭제(deque) O(1), 탐색 O(n)이 소요
• 구현 방식
  • Array-Based queue: enqueue와 dequeue 과정에서 남는 메모리가 생깁니다. 따라서 메모리의 낭비를 줄이기 위해 주로 Circular queue형식으로 구현을 합니다.
  • List-Based: singly-lilnked list로 구현, 재할당이나 메모리 낭비의 걱정을 할 필요가 없어집니다.
• 활용예시
  • Cache구현, 프로세스 관리, 너비우선탐색(BFS)등에 사용

우선순위 큐

• 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
• Priority queue는 push $O(logn)$ , pop $O(logn)$
• Heap을 기반으로 구현

Map

• 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조
• 레드 블랙 트리 자료구조를 기반으로 형성되고, 삽입하면 자동으로 정렬된다.
• 해시 테이블을 구현할때 쓰인다.

Set

• 특정 순서에 따라 고유한 요소를 저장하는 컨테이너
• 중복 요소는 없고 오로지 unique 값만 저장하는 자료구조