큐에 있는 push, pop, back 기능이 push_front, push_back, pop_front, pop_back, front, back 동작으로, 방향을 가진 세부 동작이 된다. 추가로 c++ 기준 덱은 임의의 인덱스로 접근하는 random access를 지원한다.
그런데 이렇게 동작하는 자료구조를 어떻게 하면 효율적으로 만들 수 있을까?
인덱스 접근을 허용하는 형태 (= array, vector 등 메모리가 연속된 자료구조)를 이용한다면 임의 접근과, push_back, pop_back 등은 효율적이겠지만 앞쪽을 대상으로 한 연산이 발생한 경우 매번 값을 한 칸씩 밀어줘야 하는 오버헤드가 발생한다.
만약 연속적인 메모리 할당 후, 중간지점에서 시작한다고 하더라도 앞쪽과, 뒤쪽의 연산이 균형을 이루지 않는다면 결국 한쪽으로 치우치게 될 것이고 그 치우침을 맞춰주거나, 새롭게 공간을 확보하는 행위가 모두 불필요한 오버헤드가 된다.
반대로 비 연속적인 메모리 할당을 하는(= 연결 리스트 등) 형태로 구현한다면 확실히 앞뒤 방향의 연산은 효율적으로 지원되지만, 인덱스 접근 행위에 N/2 회의 탐색이 필요할 수 있다.
이 모두를 어느 정도 만족시키기 위해 덱은 일정 단위의 연속적 메모리를 할당하는 블록을, 비 연속적인 자료구조로 묶어서 이용한다.
이를 직접 구현하기 위해서는 map이라는 자료구조에 대하여 알아야 한다. 우선 맵에 대하여 잘 모른다면 맵을 선행 학습하고 돌아오자.
시작에 앞서, 덱에 1~8의 값을 넣어둔 상태라고 가정하자. 이 덱은 데이터 4개가 하나의 블록을 이루는 형태이다.
값이 예쁘게 들어가있다, 아래의 블록이 담긴 표는 맵이며, 위의 블록은 4칸짜리 배열이라고 생각해도 된다.
같은 블록내의 값들은 메모리가 연속적으로 할당되어 있으며, 각 블록 간에는 메모리의 연관성이 없다. (= 각각 새롭게 동적으로 할당되었다.)
위 상태에서 push front 연산으로 값 0을 넣으려 한다, 그렇다면 먼저 현재 가지고 있는 블록 중 가장 작은 블록에 빈 공간이 있는지 확인 후, 빈 공간이 없다면 새로운 블록을 만든다. 이를 블록 0이라고 하자
값 0이 블록0의 맨 뒤에 들어간다는 점이 당연하다고 느껴졌으면 좋겠다. 당연하다고 느껴지지 않는다면 왜 값이 블록의 뒤쪽에 들어가야 하는지 생각해보자. 약간의 힌트를 적자면, 이 블록 0은 앞쪽 연산만을 대상으로 만들어진 블록은 아니라는 점과, 인덱스 접근이 가능해야 한다는 점이다.
값 -1을 push_front 한다면 위와 같은 상태가 된다.
값 9를 push_back 한다면 위와 같은 상태가 된다.
위의 예시를 통해 앞, 뒤 방향 동작을 보였다.
이 상황에서 어떻게 하면 인덱스 접근을 효율적으로 진행할 수 있을까?
아래의 이미지에서 "6번째 값에 최대한 빠르게 접근하는" 방법을 생각해보자.
Df = 맨 앞 블록의 데이터 개수, 여기서는 2. Db = 한 블록당 데이터 개수, 여기서는 4. Index = 입력받은 인덱스, 여기서는 6번째 칸 이므로 5. (0부터 시작하는 인덱스)
