10866번 덱(deque)

#문제링크 : https://www.acmicpc.net/problem/10866

deque은 vector와 유사하지만 vector보다 컨테이너 맨앞요소의 삽입/삭제 속도가 O(1)로 더 빠르며, 그 외 임의의 요소에 접근하는 속도는 O(1)로 같고, 맨뒤요소의 삽입속도 역시 O(1)로 더 빠르다. 이유는 vector는 일정 메모리크기 이상의 할당을 요구받으면 새로운 더 큰 크기의 메모리를 할당받고 기존에 있던 메모리에서 복사해오기 때문에 삽입속도가 평균적으로 O(1)이라고 한다지만, 복사되는 경우 O(n)이 되기 때문에 deque이 여러모로 더 속도가 빠르다. 하지만 deque은 vector와 같이 메모리상에 연속적인 공간에 존재하지 않을 수 있고, 요소가 존재하는 블록의 주소값을 저장하는 새로운 메모리 공간이 필요하므로 vector에 비해 속도는 빠르지만 메모리는 더 많이 잡아먹는다. 만약 블록의 주소값을 저장하는 메모리 공간이 가득차게 되면 vector와 같이 더 큰 새로운 공간을 할당받고 저장되어 있는 주소값을 전부 복사해 가지만 이것 역시 vector보다는 복사속도가 빠르다. 이유는 vector는 객체 요소값을 복사하는 반면에 deque은 객체 자료형보다 작은 크기인 주소값을 복사하므로 그렇다.

※주의사항

1. deque 함수 이름 유의해서 사용.

2. vector와 마찬가지로 iterator 사용할 때, 중간에 값을 삭제/추가하게 되면 사용하던 반복자가 기존 반복자의 기능상실.

헤더부분

Main Code