Special Effects FX 스스로를 감동시켜야 최선을 다 한 것이다.

덱의 이해

- 덱은 앞으로도 뒤도로 넣을 수 있고, 앞으로도 뒤도로 뺄 수 있는 자료구조이다.

deque은 double-ended queue를 줄여서 표현한 것으로, 양방향으로 넣고 뺄 수 있는다는 사실에 초점이 맞춰져서 지어진 이름이다.

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

덱 자료구조의 ADT

void DequeInit(Deque * pdeq);

- 덱의 초기화 진행

int DQIsEmpty(Deque * pdeq);

- 덱이 빈 경우 true, 아니면 false

void DQAddFirst(Deque * pdeq, Data data);

- 덱의 머리에 데이터를 저장

void DQAddLast(Deque * pdeq, Data data);

- 덱의 꼬리에 데이터를 저장

Data DQRemoveFirst(Deque * pdeq);

- 덱의 머리에 위치한 데이터를 반환, 소멸

Data DQRemoveLast(Deque * pdeq);

- 덱의 꼬리에 위치한 데이터를 반환, 소멸

Data DQGetFirst(Deque * pdeq);

- 덱의 머리에 위치한 데이터를 소멸하지 않고 반환

Data DQGetLast(Deque * pdeq);

- 덱의 꼬리에 위치한 데이터를 소멸하지 않고 반환

※ 참고로 Deque는 '디큐'로 읽기 쉽다. 그럼에도 불구하고 '덱'으로 발음하는 이유는 '디큐'로 발음할 경우 큐의 dequeue 연산과 그 발음이 같아져서 이 둘을 구분하기 어렵기 때문이다. 이것이 크게 중요한 것은 아니지만, 혼란을 줄 수 있으므로 가급적 '덱'으로 읽으면 좋다.

덱의 구현

덱도 큐와 마찬가지로 배열을 기반으로, 그리고 열결 리스트를 기반으로도 구현이 가능하다. 

하지만 덱의 구현에 가장 어울린다고 알려진 '양방향 연결 리스트'를 기반으로 덱을 구현하는 것이 좋은 선택일 수 있다.

양방향 연결 리스트가 단방향 연결 리스트보다 덱의 구현에 더 잘 어울리는 이유는 다음 함수의 구현과 관련이 있다. 

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

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

Header file

Source file

Main file

실행 결과