자료구조(7) 덱

덱은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조!

 

덱은 양방향으로 넣고, 양방향으로 뺄 수 있는 자료구조이기에 스택과 큐의 특성을 모두 갖는, 혹은 스택과 큐를 조합한 형태의 자료구조로 이해되고 있다.

 

덱도 배열을 기반으로, 그리고 연결 리스트 기반으로도 구현이 가능하다. 하지만 우리는 덱의 구현에 가장 어울린다고 알려진 "양방향 연결 리스트"를 기반으로 덱을 구현할 것이다. 그 이유는 다음 함수와 관련이 있다.

"Data DQRemoveLast(Deque * pdeq); // 꼬리에 위치한 데이터(노드) 삭제

위 함수는 꼬리에 위치한 노드를 삭제하는 함수인데, 노드가 양방향으로 연결되어 있지 않으면, 꼬리에 위치한 노드의 삭제는 간단하지 않다. 때문에 덱의 구현에 있어서 양방향 연결 리스트는 매우 좋은 선택이다.

 

• 앞으로 넣기
• 뒤로 넣기
• 앞으로 빼기
• 뒤로 빼기

참고로 Deque는 "디큐"로 읽기 쉽다. 그러나 dequeue 연산과 그 발음이 같아져서 혼란을 줄 수 있으므로 가급적 "덱"으로 읽기 바란다.