1. vector와의 비교
1) Queue (큐)
- FIFO (First-In, First-Out) 구조
- 삽입(enqueue) → 뒤(rear) / 삭제(dequeue) → 앞(front)
- 일반적인 큐는 한쪽에서만 삽입, 다른 쪽에서만 삭제 가능
- 예제:
std::queue<int> (C++ STL)
(2) Deque (덱, Double-Ended Queue)
- 양쪽에서 삽입/삭제 가능
- 앞(front)과 뒤(back)에서 O(1)로 push/pop 가능.
- 일반 큐보다 더 유연한 자료구조
- 예제:
std::deque<int> (C++ STL)
(3) Vector (벡터)
- 배열 기반 동적 리스트
- 인덱스 기반 접근 가능 (O(1))
- 크기가 자동 조정됨 (Capacity 확장)
- 삽입/삭제 속도
- 끝에서 push/pop → O(1)
- 중간에서 삽입/삭제 → O(N)
- 앞에서 삽입/삭제 → O(N) (모든 요소 이동 필요)
- 예제:
std::vector<int> (C++ STL)
2. 동작 방식과 시간 복잡도 비교
| 연산 |
Queue (std::queue) |
Deque (std::deque) |
Vector (std::vector) |
| 삽입 (맨 뒤) |
O(1) |
O(1) |
O(1) (평균) |
| 삭제 (맨 앞) |
O(1) |
O(1) |
O(N) (앞 요소 이동 필요) |
| 삭제 (맨 뒤) |
❌ (불가능) |
O(1) |
O(1) |
| 검색 (임의 위치) |
O(N) |
O(N) |
O(1) |
| 중간 삽입/삭제 |
❌ (불가능) |
O(N) |
O(N) |
3. 각 자료구조의 특징과 활용
| 자료구조 |
특징 |
활용 사례 |
| Queue |
한쪽에서 삽입, 반대쪽에서 삭제 |
프로세스 스케줄링, BFS 탐색 |
| Deque |
양쪽에서 삽입/삭제 가능 |
LRU 캐시, 슬라이딩 윈도우 |
| Vector |
인덱스 접근 가능, 동적 크기 조정 |
동적 배열, 임의 접근 필요할 때 |