스택

LIFO(후입 선출) : 가장 마지막에 “쌓인” 데이터가 가장 먼저 삭제 되는 구조

//스택의 기본 메소드
stack.push() // 데이터 삽입
stack.pop() // 데이터 추출
stack.top() // 최상위 데이터 반환
stack.size() // 스택의 크기 반환
stack.empty() // 현재 스택이 비어 있는지 확인

큐

가장 먼저 삽입 된 데이터가 가장 먼저 삭제 되는 구조

// 큐의 기본 메소드
queue.push() // 데이터 삽입
queue.pop() // 데이터 추출
queue.front() // 큐의 첫 원소 반환
queue.back() // 큐의 마지막 원소 반환
queue.size() // 큐의 크기 반환
queue.empty() // 현재 큐가 비어 있는지 확인

힙

이진 트리 형태로 원소들을 저장 → 우선 순위가 가장 높은 데이터가 가장 위로 올라오는 구조

삽입과 삭제의 원리 기억하기!

priority_queue<?> heap; // 최대힙 생성
priority_queue<?, vector<?>, greater<?>> heap // 최소힙 생성

heap.push()
heap.pop()
heap.top()
heap.empty()
heap.empty()

셋

set 개념 자체가 순서를 보장하는 자료구조는 아니지만 c++ set은 내부적으로 레드-블랙 트리 형태로 순서를 보장함
이진 트리 형태로 원소들을 저장 -> 자신보다 작은 값은 왼쪽 노드로 큰 값은 오른쪽 노드로 이동
삭제 시 자식 노드 중 하나를 위로 가져옴
AVL(균형 트리) - 한쪽으로만 노드가 계속 쌓이는 것을 방지

맵

set과 원리가 동일하게 동작하나 key, value 타입으로 이루어져 있음
value 값은 중복을 허용하나 키값은 중복 될 수 없음

// 맵의 기본 메소드
map.insert() // 맵에 요소 삽입
map.find() // 맵에서 키값 검색
map.begin() // 맵의 시작 주소 반환
map.end() // 맵의 끝 주소 반환
map[key] = value // 맵 요소 접근