[자료구조] deque

Deque

💡 매우 빠른 push_front()와 push_back() 동작과 효과적인 임의 접근의 제공하는 유일한 컨테이너

• 덱(deque)은 양방향 큐(double-ended queue)의 약자
• 양방향으로 매우 빠르게 원소 삽입&삭제 가능
• 양방향으로 매우 빠르게 확장 가능
• 모든 원소에 임의 접근을 제공

요구사항

 1. push_front(),pop_front(),push_back(),pop_back() 동작이 O(1)의 시간 복잡도로 동작해야 한다.

 2. 모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작해야 한다.

 3. 덱 중간의 원소 삽입 삭제는 O(n)의 시간 복잡도로 동작해야한다. 

Vector와의 차이점

• 모든 원소에 접근 가능하다는 점에서 vector와 deque는 비슷하다
• 하지만 deque는 앞 뒤로 확장 가능하다는 점이 다름
  • 덱은 어느 방향으로든 빠르게 확장 가능
• 시간 복잡도는 동일하지만, 덱이 벡터 보다 살짝 빠르다

제공 함수

• 삽입
  • push_front()
  • push_back()
  • insert()
  • emplace_front()
  • emplace_back()
  • emplace()
• 삭제
  • pop_front()
  • pop_back()
  • erase()
• 조회
  • begin()
  • shrink_to_fit()
    • 저장 용량 최적화

사용 예시

• 항공기 탑승 대기열