c++ 알고리즘 공부 7 - 덱

덱은 Restricted Structure의 끝판왕과 같은 느낌의 자료구조인데, 양쪽 끝에서 삽입과 삭제가 전부 가능합니다. 참고로 자료구조의 덱은 deque고 Double Ended Queue라는 뜻을 가지고 있습니다. 우리가 하스스톤이나 유희왕에서 얘기하는 덱은 Deck라서 발음은 둘 다 덱으로 똑같긴 해도 다른 단어입니다.

 

아무튼 덱은 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조이니 스택과 큐를 덱의 특수한 예시라고 생각해도 괜찮겠습니다.

 

덱에서도 삽입, 삭제, 제일 앞/뒤 원소의 확인이 다 O(1)입니다. 그리고 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능한데 독특하게도 STL deque에서는 인덱스로 원소에 접근할 수 있습니다. STL stack, queue에서 불가능했던걸 생각하면 꽤 독특한 일입니다.

 

덱도 스택이나 큐처럼 배열 혹은 연결 리스트 둘 다를 가지고 구현할 수 있지만 배열을 이용하는게 구현이 더 쉽기 때문에 배열을 이용한 구현만 같이 다룰 것입니다.

왜 저렇게 두는거냐면, 큐에서는 앞쪽에서는 제거만 발생하고 뒷쪽에서는 삽입만 발생하다보니 배열 내에서 실제 큐에 들어간 원소들이 차지하는 공간이 점점 오른쪽으로 이동하면서 확장하는 모양이었습니다.

 

하지만 덱에서는 양쪽에서 모두 삽입이 가능합니다. 그렇기 때문에 마치 여의봉처럼 양쪽으로 확장해야 합니다. 그러면 별 생각 없이 시작 지점이 0번지로 뒀을 경우 왼쪽으로 확장을 할 수가 없게 됩니다. 대신에 시작 지점을 배열의 중간으로 둬야 합니다. 중간으로 두면 중앙에서 양쪽으로 확장이 가능합니다. 그래서 배열의 크기는 2*MX+1이고 head와 tail의 초기값은 MX인 것입니다.

 

일단 필요한 변수는 큐랑 똑같이 원소를 담을 큰 배열 한 개와 앞쪽, 뒤쪽을 가리킬 변수 두 개입니다. 이 때 head와 tail을 두는 방식도 큐와 똑같습니다. head는 가장 앞에 있는 원소의 인덱스이고 tail을 가장 뒤에 있는 원소의 인덱스 + 1입니다. 그리고 head와 tail의 초기값이 0이 아니라 MX인데 이 부분을 좀 짚고 넘어가겠습니다.