[C] 덱 (Deque) 개념 및 원형 덱 구현

개념

덱은 양방향 큐 (Double Ended Queue)의 줄임말이다.

 

이름 그대로 큐 구조가 양방향으로 되어있다. 즉, 데이터의 삽입, 삭제가 맨 앞과 맨 뒤에서 이루어지는 구조다.

(큐는 먼저 추가한 데이터부터 삭제하는 구조, 선입 선출)

 

한글 발음으로 덱, 데크로 불린다.

 

특징

1. 배열로도 구현이 가능하고, 연결 리스트로도 구현이 가능하다.

    따라서 구현한 자료구조에 따라서 해당 자료구조의 특징을 갖는다.

 

2. 데이터의 맨 앞과 맨 뒤에서만 삽입, 삭제, 접근이 필요할 때 사용하는 것이 바람직하다.

 

3. 요소의 삽입은 맨 앞, 맨 뒤에 삽입할 경우 O(1), 이외에는 구현한 자료 구조에 따라 다르다.

    요소의 삭제는 맨 앞, 맨 뒤를 삭제할 경우 O(1), 이외에는 구현한 자료 구조에 따라 다르다.

    맨 앞, 맨 뒤 원소의 접근은 O(1), 이외에는 구현한 자료 구조에 따라 다르다.

 

 

장점

1. 데이터의 앞과 뒤에서만 삽입, 삭제, 접근이 이루어질때 굉장히 빠르게 동작한다. O(1)

 

2. 나머지는 구현에 선택한 자료 구조에 대한 장점을 그대로 가져온다.

 

 

단점

1. 중간 요소를 접근하거나 중간에 삽입, 삭제가 필요한 작업이 있다면 굳이 채택할 필요가 없다.

 

2. 나머지는 구현에 선택한 자료 구조에 대한 단점을 그대로 가져온다.

 

 

상세 설명

스택, 큐, 덱과 같은 자료 구조는 배열과 연결 리스트처럼 독자적이기 보다는 이를 활용한 자료 구조라고 볼 수 있다.

따라서 이들은 모두 배열이나 연결 리스트로 구현이 가능하다.

 

 

덱은 일반적으로 head (== front)와 tail (== back)을 가지고 있다.

맨 앞에서 작업하려면 head를 사용해야 하고, 맨 뒤에서 작업하려면 tail을 사용해야 한다.

 

연결 리스트로 구현하려면 Data가 필요 없고 head, tail은 Node가 되어야 할 것이고,

배열로 구현하려면 Data는 배열의 첫 주소, head와 tail은 index가 되는 것이 구현에 편리할 것이다.

 

필자는 배열로 구현할 것이며, 따라서 데이터의 개수(Size)와 배열의 총 용량(Capacity)의 차이를 두었다.

 

배열로 구현함에 있어서 중요한 점은 원형 덱(Circular Deque)을 고려하는 것이다.

 

 

일반 배열이 위와 같이 선형이라면,

 

 

이렇게 배열의 양 끝을 이어서 원형으로 만드는 것이다.

 

덱의 특성상 양 옆에서만 데이터가 삽입, 삭제되는데,

그러다보면 head나 tail이 배열의 끝을 가리킨 상태에서 그 쪽의 데이터를 더 추가할 경우가 생긴다.

그 때 만약 배열에 안 쓰는 공간이 반대편에 더 있을 경우, 데이터를 추가할 수 없는 경우가 생기기 때문이다.

 

따라서 그 끝을 가리키고 있는 head나 tail을 배열의 반대편 끝으로 옮겨주면서 데이터를 추가할 수 있다.

 

연결 리스트는 이러한 과정이 필요 없이, tail node와 head node를 이어주기만 하면 끝인데,

배열은 이를 구현하려면 꽤나 복잡하다.

 

그러나 배열은 배열만의 이점이 있는 법, 따라서 필자는 원형 덱을 배열로 구현했다.

 

 

구현

설명에 앞서 참고해야할 사항 몇 가지

 

우선 덱의 할당과 해제는 프로그래머에게 맡긴다.

따라서 덱은 이미 할당되어 있다는 가정을 한다.

 

또한 다음과 같은 사항은 코드의 가독성 문제 등으로 염려에 두지 않았다.
  1. 함수의 덱(deq) 매개변수가 NULL pointer일 경우
  2. malloc() 이 실패한 경우
  3. free() 후 댕글링 포인터

  4. size, capacity, head, tail의 overflow

 

구조체

typedef struct deque
{
	int* data;
	int size;
	int capacity;
	int head;
	int tail;
} deque;

위에 설명한대로다.

 

배열의 주소(data), 데이터의 개수(size), 배열의 총 용량(capacity),

제일 첫 번째 데이터의 인덱스(head), 제일 마지막 데이터의 인덱스(tail)이다.

 

초기화

void initialize(deque *deq)
{
	deq->data = NULL;
	deq->size = 0;
	deq->capacity = 0;
	deq->head = -1;
	deq->tail = -1;
}

덱의 할당은 프로그래머에게 맡기므로 모든 데이터를 NULL 또는 0으로 초기화해준다.

 

head와 tail을 -1로 해주는 이유는, 데이터가 없기 때문에 해당 index도 존재하지 않기 때문이다.

 

맨 뒤에 데이터 추가

void push_back(deque *deq, int data)
{
	if (deq->size == deq->capacity)
		re_allocate(deq, deq->capacity * 2);
	
	if (deq->head == -1)
	{
		deq->head = 0;
		deq->tail = 0;
	}
	else if (deq->tail == deq->capacity - 1)
		deq->tail = 0;
	else
		++deq->tail;
	deq->data[deq->tail] = data;
	++deq->size;
}

여기서도 동적 배열 파트에서 사용한 재할당 함수를 사용하는데, 설명의 이해를 돕기 위해 조금 이따가 설명하도록 하겠다.

 

우선, 데이터의 개수가 배열의 총 용량과 같다면 (데이터가 꽉 찼다면)

현재 용량의 두배로 늘려준다 라고만 이해하고 넘어가자.

 

예외적으로 deq의 head가 -1이라면 (데이터가 비어있다면), head와 tail을 모두 0으로 만들어준다.

 

이후 원형 덱이므로 아래의 그림처럼 흘러가게 된다.

 

 

데이터가 비어있는 상황이 아닌 경우, deq의 tail을 1 증가시켜준다.

단, 원형 덱이므로 deq의 tail이 최대 index (capacity - 1)에 도달했을 경우 최소 index (0)으로 옮겨준다.

 

이후 deq의 data의 tail에 인자로 받은 data를 넣어주고, size를 증가시켜준다.

 

맨 앞에 데이터 추가

void push_front(deque *deq, int data)
{
	if (deq->size == deq->capacity)
		re_allocate(deq, deq->capacity * 2);

	if (deq->head == -1)
	{
		deq->head = 0;
		deq->tail = 0;
	}
	else if (deq->head == 0)
		deq->head = deq->capacity - 1;
	else
		--deq->head;
	deq->data[deq->head] = data;
	++deq->size;
}

push_back()과 똑같이 공간이 부족하면 재할당 해준 뒤, 덱이 비어있을 때 예외 처리도 해준다.

 

 

데이터가 비어있는 상황이 아닌 경우, deq의 head를 1 감소시켜준다.

이번에도 원형 덱이므로 head가 최소 index (0)에 도달했을 경우 최대 index (capacity - 1)로 옮겨준다.

 

이후 deq의 data의 tail에 인자로 받은 data를 넣어주고, size를 증가시켜준다.

맨 뒤의 데이터 삭제

void pop_back(deque *deq)
{
	if (deq->size == 0)
		return;
	
	if (deq->size == 1)
	{
		deq->head = -1;
		deq->tail = -1;
	}
	else if (deq->tail == 0)
		deq->tail = deq->capacity - 1;
	else
		--deq->tail;
	--deq->size;
	return;
}

먼저 deq의 size가 0일 때 예외처리 해준다.

 

deq의 size가 1일 경우 마지막 원소이므로 head와 tail을 모두 -1로 다시 바꿔준다.

 

데이터를 삭제할 때도 추가할 때와 마찬가지로 원형 덱의 구조를 유지해야한다.

 

이후 deq의 size를 감소시켜준다.

 

맨 앞의 데이터 삭제

void pop_front(deque *deq)
{
	if (deq->size == 0)
		return;
	
	if (deq->size == 1)
	{
		deq->head = -1;
		deq->tail = -1;
	}
	else if (deq->head == deq->capacity - 1)
		deq->head = 0;
	else
		++deq->head;
	--deq->size;
	return;
}

이 역시 deq의 size가 0일 때 예외처리 해준다.

 

deq의 size가 1일 경우 마지막 원소이므로 head와 tail을 모두 -1로 다시 바꿔준다.

 

이 때도 역시 원형 덱의 구조를 유지해야한다.

 

이후 deq의 size를 감소시켜준다.

 

재할당

static void re_allocate(deque *deq, int capacity)
{
	if (capacity == 0)
		capacity = 1;

	int* new_data = (int*)malloc(capacity * sizeof(int));

	for (int i = 0; i <= deq->tail; ++i)
		new_data[i] = deq->data[i];
	
	if (deq->head > deq->tail)
	{
		for (int i = 0 ; i < deq->capacity - deq->head; ++i)
			new_data[capacity - 1 - i] = deq->data[deq->capacity - 1 - i];
		deq->head = capacity - (deq->capacity - deq->head);
	}
	free(deq->data);
	deq->data = new_data;
	deq->capacity = capacity;
}

드디어 미뤄두었던 재할당 부분이다.

동적 배열의 재할당과 비슷하지만, 데이터를 복사하는 부분에서는 분명히 다르게 처리해야한다.

 

 

먼저, 위의 그림처럼 평범한 경우에는 그냥 2배 늘려준 후 그대로 복사하면 끝이다.

 

하지만 원형 덱은 위에서 보았듯이 이렇게 평범하게만은 생기지 않았다.

 

 

어느 순간 tail이 head보다 앞에 있는 경우가 생긴다.

이럴 때는 tail까지는 그냥 복사해준 뒤에, head부터는 증가된 새 배열의 오른쪽 끝에 붙여서 복사해줘야 한다.

그래야 원형 덱이 정상적으로 돌아가게 될 것이다.

 

deq->capacity - deq->head가 head부터 배열 끝까지의 원소 개수이고

기존 배열의 끝부터 새 배열의 끝으로, 끝에서부터 시작하여 head까지 복사하는 방법이다.

 

배열 용량 사전 설정

void reserve(deque *deq, int capacity)
{
	if (capacity <= deq->capacity)
		return;
	
	re_allocate(deq, capacity);
}

이 역시 동적 배열과 마찬가지로 원소가 추가되며 배열을 계속 두 배씩 재할당 한다면 오버헤드가 커진다.

 

이를 방지하기 위해 쓸 만큼을 미리 할당해두는 것이 바람직하다.

 

인자로 받은 할당할 capacity가 현재 deq의 capacity보다 작거나 같으면 진행하지 않는다.

 

모든 데이터 삭제

void clear(deque *deq)
{
	free(deq->data);
	initialize(deq);
}

deq의 data를 free해준 뒤 앞서 만들었던 초기화 함수로 초기화 시켜준다.

 

테스트

 

테스트를 위해 안 쓰는 데이터는 0으로 바꾸고, "-"로 출력하게끔 잠시 바꾸었다.

 

리눅스 환경에서 여러 컴파일 옵션을 줘서 테스트했고

메모리 누수 포함 에러가 (아직은) 없는 것을 확인했다.

 

↓ 테스트 코드 확인하기

#include <stdio.h>
#include "Deque.h"

// Test for Deque.c

void print_deque(deque* deq)
{
	printf("[size:%d, cap:%d, head: %d, tail: %d] ", deq->size, deq->capacity, deq->head, deq->tail);
	for (int i = 0; i < deq->capacity; ++i)
	{
		if (deq->data[i] == 0)
			printf("- ");
		else
			printf("%d ", deq->data[i]);
	}
	
	printf("\n");
}

int main()
{
	deque deq;

	printf("----- initialize -----\n");
	initialize(&deq);
	print_deque(&deq);

	printf("\n----- push_back -----\n");
	for (int i=1; i<5; ++i)
	{
		push_back(&deq, i);
		print_deque(&deq);
	}

	printf("\n----- pop_back -----\n");
	for (int i=1; i<3; ++i)
	{
		pop_back(&deq);
		print_deque(&deq);
	}

	printf("\n----- push_front -----\n");
	for (int i=5; i<9; ++i)
	{
		push_front(&deq, i);
		print_deque(&deq);
	}

	printf("\n----- push_back again! -----\n");
	for (int i=10; i<13; ++i)
	{
		push_back(&deq, i);
		print_deque(&deq);
	}

	printf("\n----- pop_front -----\n");
	for (int i=1; i<3; ++i)
	{
		pop_front(&deq);
		print_deque(&deq);
	}

	printf("\n----- reserve -----\n");
	reserve(&deq, 25);
	print_deque(&deq);

	printf("\n----- clear -----\n");
	clear(&deq);
	print_deque(&deq);

	printf("\n----- edge cases -----\n");
	clear(&deq);			// double clear
	print_deque(&deq);

	reserve(&deq, -1);		// reserve by lower than size
	print_deque(&deq);

	pop_back(&deq);			// pop at empty deqtor
	print_deque(&deq);

	push_back(&deq, 1);		// use after clear
	print_deque(&deq);

	push_front(&deq, 2);		// use after clear
	print_deque(&deq);

	reserve(&deq, 10);
	print_deque(&deq);

	push_back(&deq, 3);		// use after reserve
	print_deque(&deq);

	push_front(&deq, 4);		// use after reserve
	print_deque(&deq);
	clear(&deq);
}

 

 

마무리

스택과 큐, 덱을 포스팅하려고 하니

앞서 포스팅한 연결 리스트와 동적 배열에서 다 했던 것들이어서 새로운 방법으로 구현해보았다.

 

생각보다 까다로운 작업이지만, 한 번쯤 구현해보면 도움이 많이 될 것이다.

 

중간 요소의 삽입 삭제도 필요하면 구현할 수는 있으나 동적 배열과 똑같아서 하지 않았다.

 

필요하다면 동적 배열 파트에서의 구현을 참고해보면 좋을 것이다.

https://sikpang.tistory.com/12?category=1090697

[C] 동적 배열 (Dynamic Array) 개념 및 구현

 

마지막으로 전체 코드 링크 (테스트용과 다름)

https://github.com/SikPang/DataStructures/tree/main/C_Deque%20(Circular)

 

개인 공부용 포스팅인 점을 참고하시고, 잘못된 부분이 있다면 댓글로 남겨주시면 감사드리겠습니다.