stl에 구현되어 있는 deque의 할당 정책은 원소 추가 시 메모리가 부족할때마다 일정한 크기의 새로운 메모리 블록을 할당하여 이전 메모리를 제거하거나 이전 원소를 복사하는 등의 연산을 수행하지 않는다 라고 알고있는데요 20:26초 영상에는 데이터 복사를 수행 하내요? 저희가 구현하고 있는 queue는 stl에 구현되어 있는 deque와는 다른 개념 인가요??

deqeue는 Double Ended Queue라서 queue와는 다른 개념입니다. dequeue는 stack/queue의 기능을 모두 갖고 있습니다. STL 구현에서 dequeue는 복사를 하지 않도록 블록 단위로 띄엄 띄엄 메모리를 할당하는 대신, 접근할 때 위치를 찾기 위해 아주 약간의 연산 비용이 추가됩니다. 현재 연습용으로 구현한 queue는 vector 와 비슷한 방식의 동적 배열을 이용한 것입니다. FIFO의 특징만 유지하면 queue라고 볼 수 있고 이것을 연결 리스트 방식으로 할지, 동적 배열 방식으로 할지 기타 방식으로 할지는 사실 꼭 정해진 바 없습니다.

인프런 커뮤니티 질문&답변

선생님 queue 할당 정책에 관한 질문이 있습니다