vector: 연속된 메모리 블록. 인덱싱/순회 자유롭지만 맨 앞 삽입/삭제는 O(n) (기존 원소를 다 밀어야 함)queue: 컨테이너 어댑터. 내부적으로 기본값은deque를 사용.push()(뒤에 추가),pop()(앞에서 제거),front(),back(),size(),empty()만 제공 — 인덱싱/순회 불가- "이 자료구조는 FIFO로만 쓴다"는 의도를 컴파일 타임에 강제하는 역할도 겸함
deque는 하나의 연속 블록이 아니라, 고정 크기 블록(chunk) 여러 개 + 그 블록들의 주소를 담은 지도(map) 구조.
[블록1: 원소들...] [블록2: 원소들...] [블록3: 원소들...]
↑ 블록 내부는 연속 배열(캐시 친화적), 블록끼리는 포인터로 연결
- 각 블록은 처음부터 여유 슬롯을 앞뒤로 남겨두고 할당됨
- 앞/뒤에 여유 슬롯이 있으면 -> 그냥 그 자리에 쓰고 시작/끝 커서만 이동 (기존 원소 이동 없음)
- 여유 슬롯이 다 떨어지면 -> 새 블록을 만들어 지도에 등록 (역시 기존 원소 이동 없음)
→ vector의 push_back 상수배 재할당 전략을, 블록 단위로 양쪽 끝에 동시에 적용한 것과 같음. 재할당 비용이 "전체 복사"가 아니라 "블록 하나 추가"라 훨씬
저렴함.
deque는 큐 전용이 아니라 O(1) 인덱싱(d[i])까지 지원하는 범용 컨테이너로 설계됨.
| 양 끝 O(1) | O(1) 인덱싱 | 캐시 효율 | |
|---|---|---|---|
vector |
✗(앞쪽) | ✓ | ✓ |
| 순수 링크드 리스트 | ✓ | ✗ (O(n)) | ✗ |
deque (블록+지도) |
✓ | ✓ | △ (블록 내부만) |
- 링크드 리스트는 원소 하나마다 개별 힙 할당 + 앞뒤 포인터 필요 →
int하나 저장하는 데 포인터 오버헤드가 더 큼 deque는 블록 단위로 뭉쳐서 할당하므로 이 오버헤드가 훨씬 적고, 인덱싱도 O(1)로 가능
std::queue는 기본 내부 컨테이너로 deque를 재사용 — 큐 전용 자료구조를 새로 안 만들고 이미 다재다능하게 설계된 deque를 어댑터로 감싼 것.
같은 "양 끝 O(1)"이라는 목표를, 언어마다 다른 방식으로 구현함.
- C++
std::deque: 블록 + 지도 (chunked) - Java
ArrayDeque, RustVecDeque: 원형 버퍼(circular buffer). 배열 하나에 시작/끝 인덱스를 순환시킴 (% capacity). 꽉 차면vector처럼 통째로 재할당. 구조가 단순하고 캐시 효율 좋음 - Java
LinkedList, Gocontainer/list: 순수 링크드 리스트. 양 끝 O(1)은 쉽지만 인덱싱 불가, 캐시 효율 최악 - Python
collections.deque: C++과 유사하게 고정 크기 블록의 이중연결리스트 - Go: 표준 라이브러리에 전용 데크 없음. 슬라이스 기반 원형 버퍼를 직접 구현하거나
container/list사용