[C++] 덱 std::deque

std::deque(Double Ended Queue)는 C++ 표준 라이브러리에서 제공하는 시퀀스 컨테이너 중 하나로, 양쪽 끝에서 삽입과 삭제를 효율적으로 수행할 수 있는 자료구조 입니다. std::deque는 스택과 큐의 기능을 모두 제공하며, std::vector과 유사하지만 몇가지 차이점이 있습니다.

 

 

주요 특징 :

1. 양쪽 끝에서 삽입과 삭제가 가능 : deque는 양쪽 끝에서 모두 삽입과 삭제 작업을 상수시간에 수행할 수 있습니다.
2. 임의 접근 가능 : deque는 vector처럼 임의 접근을 지원하므로, 인덱스를 사용하여 특정 위치의 요소에 접근할 수 있습니다.
3. 동적 크기 : deque는 내부적으로 동적 크기 조정을 수행하므로, 필요에 따라 크기가 자동으로 조정됩니다.
4. 메모리 할당 방식 deque는 여러 블록의 메모리를 할당받아 데이터를 저장하며, 이를 통해 양쪽 끝에서의 효율적인 삽입과 삭제를 가능하게 합니다.

 

주요 멤버 함수 :

• push_back(value) : 컨테이너의 끝에 요소를 추가합니다.
• push_front(value) : 컨테이너의 앞에 요소를 추가합니다.
• pop_bback() : 컨테이너의 끝 요소를 제거합니다.
• pop_front() : 컨테이너의 앞 요소를 제거합니다.
• front() : 첫번째 요소를 참조합니다.
• back() : 마지막 요소를 참조합니다.
• size() : 컨테이너에 저장된 요소의 개수를 반환합니다.
• empty() : 컨테이너가 비어 있는지 확인합니다.
• operator[] : 인덱스를 사용하여 요소에 접근합니다.

 

 

std::deque 와 std::vector의 차이점 

• 메모리 연속성 : vector는 단일 연속된 메모리 블록에 데이터를 저장하지만, deque는 여러 블록에 나누어 저장합니다.   이 때문에 deque는 양쪽 끝에서의 삽입과 삭제가 빠르지만 vector처럼 모든 요소가 메모리상에 연속적으로 저장되지는 않습니다.
• 성능 차이 : deque는 양쪽 끝에서의 삽입과 삭제가 O(1)에 가깝게 수행되며, vector는 push_back은 빠르지만 push_front나 임의의 위치에 삽입하는 경우 O(n)의 시간 복잡도를 가질 수 있습니다.