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

실행 결과

F(Front), R(Rear)

F는 큐의 머리를, R은 큐의 꼬리를 가리키는 일종의 변수를 의미.

R이 배열의 끝에 도달하면, 다시 맨 앞으로 이동시켜서 R이 회전하게 만든다. 물론 R을 뒤쫗아 가는 F도 배열의 끝에 도달하면 회전해야 한다. 그리고 이러한 방식으로 동작하는 배열 기반의 큐를 가리켜 '원형 큐(Circular Queue)' 라 한다. 

논리적으로 배열이 원형의 형태를 갖춘다고 해서 붙여진 이름이다.

원형 큐의 문제점

원형 큐는 F와 R의 위치만 가지고는 꽉 찬 경우와 텅 빈 경우를 구분할 수가 없다.

원형 큐의 문제해결

배열을 꽉 채우지 않는다. 꽉 차면 구분이 안되니 꽉 채우지 않는다.

즉, 배열의 길이가 N이라면 데이터가 N-1개 채워졌을 때, 이를 꽉 찬 것으로 간주한다.

이렇게 하면 저장 공간 하나를 낭비하지만 이로 인해서 문제 하나가 해결이 되는 셈이니 잃는 것보다 얻는 것이 더 많다.

실제 큐의 구현을 위해서 인지하고 있어야 하는 2가지

1. enqueue 연산 시, R이 가리키는 위치를 한 칸 이동시킨 다음에, R이 가리키는 위치에 데이터를 저장한다.

2. dequeue 연산 시, F가 가리키는 위치를 한 칸 이동시킨 다음에, F가 가리키는 위치에 저장된 데이터를 반환 및 소멸한다.

이 중에서 특히 dequeue 연산 시에도 F가 가리키는 위치를 우선 한 칸 이동한다는 사실을 잊어선 안된다.

이로써 구현할 큐의 특성 두 가지를 다음과 같이 추가로 정리할 수 있다.

# 원형 큐가 텅 빈 상태        -        F와 R이 동일한 위치를 가리킨다.

# 원형 큐가 꽉 찬 상태        -        R이 가리키는 위치의 앞을 F가 가리킨다.

Header File

Source File

Main File