바킹독 알고리즘 0x07강 덱 요약본

1. 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조이다. double ended queue 줄여서 deque 덱

2. 원칙적으로는 맨 뒤와 맨 앞 요소가 아닌 다른 요소들의 확인이나 변경이 불가능한, 특이하게 덱 STL 에서는 인덱스를 이용해 접근 가능하다.

3. 헤드와 테일을 두는 방식은 큐와 동일하나, 헤드와 테일의 초기값이 0이 아닌 배열의 중간 인덱스이다. 왜냐면 큐에서는 오른쪽으로만 확장하지만, 덱에서는 여의봉처럼 양쪽으로 확장하기 때문에 그렇다. 그래서 배열을 만들 때 크기를 2*MX + 1 로 해 두어야 한다.

4. STL 덱 

 front 에서도 O(1) 에 추가/제거가 가능하다. 그리고 Insert erase 등도 있어서 STL vector 와 비슷한 느낌이다. 다만 vector 와 달리 덱은 모든 원소들이 메모리 상에 연속하게 배치되어 있지 않다.

5. 앞쪽에서의 추가/삭제가 필요하지 않다면 STL vector 를, 그렇지 않다면 STL deque 를 사용하자.