자료구조 덱 (deque) : 앞과 뒤에서 추가되고 삭제된다.

 자료구조의 덱, 그러니까 deque는 queue하고 비슷합니다. front와 back, 이렇게 2개의 포인터 있습니다. 그런데, 큐가 front에서 삭제가 일어나고, back에서 삽입 연산이 일어나는데 비해서, 덱은 front에서도 삽입과 삭제가, back에서도 삽입과 삭제가 일어납니다.

 

 이 연산만 구현하려면, 사실 List로 구현하는 게 제일 간단해 보입니다.

 

 

---

 먼저 다음과 같이 초기화를 시켜 봅시다.

 

 

 그러면 이 때가 비어있는 상태일 겁니다. head->next가 tail이고, tail->prev가 head일 때, empty 상태라고 판단할 수 있습니다. 저는 이 두 개의 더미를 인위적으로 잇기만 하였습니다. 여기에서 push_front 연산을 수행해 봅시다. 이것은 맨 앞에 원소를 추가하는 것입니다. 차례대로 앞에 1, 3을 넣어보도록 하겠습니다.

 

 

 그럴려면, 보라색 노드를 가리키는 head와 초록색 노드를 가리키는 head->next를 얻어와야 할 겁니다. 1을 중간에 끼워넣기 전에, head->next의 값을 temp에 대입해 보겠습니다. 그 다음에, 보라색 다음에 새로 추가된 노드가, 새로 추가된 노드 뒤에 초록색 노드가 연결되게 하면 될 거에요.

 

 

 다음에 3을 앞에 추가해 봅시다. 마찬가지로, head와 head->next를 보라색과 연두색으로 표시해 보았습니다.

 

 

 그러면 이 상태에서, 3을 보라색 뒤에, 그리고 연두색 앞에 추가하면 될 겁니다. 마찬가지로, 초록색을 가리키는 것이 temp라고 하고, 보라색을 가리키는 것은 List의 head 값이니까요.

 

 

 그러면 보라색 뒤에 3을, 3 뒤에 초록색이 오게끔 연결해 주면 됩니다.

 

 

---

 push_back은 어떨까요? 이것은 맨 뒤에 추가를 해야 하기 때문에 먼저 tail이 가리키고 있는, 그러니까 List의 맨 끝을 탐색합니다. 제가 주황색으로 칠한 부분입니다.

 

 

 이 부분입니다. 그러면 2는 어디와 어디 사이에 추가 되어야 할까요? 주황색 앞에는 실제 맨 뒤에 있는 원소인 1이 있습니다. 이 노드를 연두색으로 표시해 봅시다.

 

 

 그러면 연두색과 주황색 사이에 추가되어야 한다는 것을 알 수 있습니다.

 

 

 따라서 연두색 다음에 새롭게 추가되는 노드인 2를, 2 다음에 tail이 오게끔 연결해 주면 됩니다.

 

 

---

 front와 back은 각각 가장 앞에 있는 원소와 가장 뒤에 있는 원소를 리턴합니다. deque가 비어 있다면, 이 연산을 수행하면 안 됩니다. 즉, head->next가 tail일 때에는 수행하면 안 됩니다. 물론 더미 값을 리턴해도 되긴 됩니다만, 비어 있다는 처리는 해 주셔야 겠지요.

 

 

 그렇지 않다면, front 함수가 호출되었을 때에는 head->next에 있는 값을, back이 호출이 되었을 때에는 tail->prev에 있는 값을 돌려주면 됩니다. 이제 pop_front()와 pop_back()이 남았네요. 맨 앞의 것을 제거하고, 다음에 맨 뒤의 것을 제거해 봅시다.

 

 제거 함수는 remove 하기 전에, empty한지 확인해 주어야 하는데요. head->next가 tail이면 비어있습니다. 그렇지 않다면 pop_front나 pop_back을 호출할 수 있습니다.

 

 

 먼저 앞의 것을 제거해야 하는 경우, head->next가 제거되어야 합니다. 그러면 head->next의 값을 rm, head->next->next의 값을 rm_next라고 합시다.

 

 

 그러면 이런 식으로 될 텐데요. head와 rm_next를 양방향으로 이어주면 된다는 것을 알 수 있어요. 이제 pop_back 연산을 수행해 볼까요?

 

 

 그러면 우리는 2를 제거해야 하는데요. 2는 tail->prev임을 알 수 있어요. 이게 주황색 부분입니다. 이 값을 rm이라 하면, rm은 주황색으로 색칠된 노드를 가리킵니다. 주황색 부분의 이전 원소인 1은 tail->prev->prev입니다. 이 값을 rm_prev라 합시다.

 

 제가 제거해야 할 것은 주황색으로 색칠된 것인데요. 그럴려면, rm_prev와 tail을 양방향으로 이어버리면 됩니다.

 

 

 그러면 맨 뒤에 있었던 2가 제거되었다는 것을 알 수 있어요. 덱은 앞과 뒤에서 push, pop 연산이 일어날 수 있어요. ps에서는 그렇게 자주 보이는 편은 아닙니다만, 간혹 가다가 나오기 때문에 아시면 좋을 듯 싶습니다.