덱(Deque)에 대해서

덱이란?

양방향 대기열(Double ended queue)은 아래 그림처럼 시작과 끝 지점에서 양쪽으로 데이터를 인큐하거나 디큐하는 자료구조입니다.

덱을 구현하는 프로그램

덱을 구현하는 프로그램을 구현해봅시다.
덱은 큐와 유사하며 양방향으로 enque와 deque가 할수 있습니다. 링크텍스트 다음 링크는 큐에 대한 링크입니다. 아래의 덱을 구현하는 프로그램은 링크의 큐을 구현하는 프로그램에서 덱으로 활용한 것입니다.

아래는 IntDequeue.h 소스파일입니다.

/* int형 큐 IntDequeue.h(헤더) */
#ifndef ___IntDequeue
#define ___IntDequeue

/*--- 큐를 구현하는 구조체 ---*/
typedef struct {
	int max;	/* 큐의 최대 용량 */
	int num;	/* 현재 요소의 개수 */
	int front;	/* 프런트 */
	int rear;	/* 리어 */
	int* que;	/* 큐의 첫 요소에 대한 포인터 */
} IntDequeue;

/*--- 큐 초기화 ---*/
int Initialize(IntDequeue* q, int max);

/*--- 큐에 맨 앞에 데이터 인큐 ---*/
int EnqueFront(IntDequeue* q, int x);

/*--- 큐에 맨 뒤에 데이터 인큐 ---*/
int EnqueRear(IntDequeue* q, int x);

/*--- 큐에서 맨 앞의 데이터를 디큐 ---*/
int DequeFront(IntDequeue* q, int* x);

/*--- 큐에서 맨 뒤의 데이터를 디큐 ---*/
int DequeRear(IntDequeue* q, int* x);

/*--- 큐에서 맨 앞의 데이터를 피크 ---*/
int PeekFront(const IntDequeue* q, int* x);

/*--- 큐에서 맨 뒤의 데이터를 피크 ---*/
int PeekRear(const IntDequeue* q, int* x);

/*--- 모든 데이터를 삭제 ---*/
void Clear(IntDequeue* q);

/*--- 큐의 최대 용량 ---*/
int Capacity(const IntDequeue* q);

/*--- 큐에 저장된 데이터의 개수 ---*/
int Size(const IntDequeue* q);

/*--- 큐가 비어 있는가? ---*/
int IsEmpty(const IntDequeue* q);

/*--- 큐가 가득 찼는가? ---*/
int IsFull(const IntDequeue* q);

/*--- 큐에서 검색(요소 인덱스) ---*/
int Search(const IntDequeue* q, int x);

/*--- 큐에서 검색(요소 맨 앞 요소부터 몇번째 값) ---*/
int Search2(const IntDequeue* q, int x);

/*--- 모든 데이터 출력 ---*/
void Print(const IntDequeue* q);

/*--- 큐 종료 ---*/
void Terminate(IntDequeue* q);
#endif

아래는 IntDequeue.c 소스파일입니다.

/* int형 큐 IntDqueue(소스) */
#include <stdio.h>
#include <stdlib.h>
#include "IntDequeue.h"

/*--- 큐 초기화 ---*/
int Initialize(IntDequeue* q, int max)
{
	q->num = q->front = q->rear = 0;
	if ((q->que = (int*)calloc(max, sizeof(int))) == NULL) {
		q->max = 0;				/* 배열 생성에 실패 */
		return -1;
	}
	q->max = max;
	return 0;
}

/*--- 큐의 front에 데이터를 인큐 ---*/
int EnqueFront(IntDequeue* q, int x)
{
	if (q->num >= q->max)
		return -1;				/* 큐가 가득 참 */
	else {
		q->num++;
		if (q->front == 0)
			q->front = q->max;
		q->que[--q->front] = x;
		return 0;
	}
}

/*--- 큐의 rear에 데이터를 인큐 ---*/
int EnqueRear(IntDequeue* q, int x)
{
	if (q->num >= q->max)
		return -1;				/* 큐가 가득 참 */
	else {
		q->num++;
		q->que[q->rear++] = x;
		if (q->rear == q->max)
			q->rear = 0;
		return 0;
	}
}

/*--- 큐의 맨 앞에서 데이터를 디큐 ---*/
int DequeFront(IntDequeue* q, int* x)
{
	if (q->num <= 0)				/* 큐는 비어 있음 */
		return -1;
	else {
		q->num--;
		*x = q->que[q->front++];
		if (q->front == q->max)
			q->front = 0;
		return 0;
	}
}

/*--- 큐의 맨 뒤에서 데이터를 디큐 ---*/
int DequeRear(IntDequeue* q, int* x)
{
	if (q->num <= 0)				/* 큐는 비어 있음 */
		return -1;
	else {
		q->num--;
		if (q->rear == 0)
			q->rear = q->max;
		*x = q->que[--q->rear];
		return 0;
	}
}

/*--- 큐의 맨 앞 데이터를 피크 ---*/
int PeekFront(const IntDequeue* q, int* x)
{
	if (q->num <= 0)				/* 비어 있는 상태의 큐 */
		return -1;
	*x = q->que[q->front];
	return 0;
}

/*--- 큐에서 맨 뒤 데이터를 피크 ---*/
int PeekRear(const IntDequeue* q, int* x)
{
	if (q->num <= 0)				/* 비어 있는 상태의 큐 */
		return -1;
	*x = q->que[(q->rear - 1 + q->max) % q->max];
	return 0;
}

/*--- 모든 데이터 삭제 ---*/
void Clear(IntDequeue* q)
{
	q->num = q->front = q->rear = 0;
}

/*--- 큐의 최대 용량 ---*/
int Capacity(const IntDequeue* q)
{
	return q->max;
}

/*--- 큐에 쌓여 있는 데이터의 개수 ---*/
int Size(const IntDequeue* q)
{
	return q->num;
}

/*--- 큐가 비어 있나요? ---*/
int IsEmpty(const IntDequeue* q)
{
	return q->num <= 0;
}

/*--- 큐가 가득 찼나요? ---*/
int IsFull(const IntDequeue* q)
{
	return q->num >= q->max;
}

/*--- 큐에서 검색(요소 인덱스) ---*/
int Search(const IntDequeue* q, int x)
{
	int i, idx;

	for (i = 0; i < q->num; i++) {
		if (q->que[idx = (i + q->front) % q->max] == x)
			return idx;		/* 검색 성공 및 인덱스 반환*/
	}
	return -1;				/* 검색 실패 */
}

/*--- 큐에서 검색(요소 맨 앞 요소부터 몇번째 값) ---*/
int Search2(const IntDequeue* q, int x)
{
	int i;

	for (i = 0; i < q->num; i++) {
		if (q->que[(i + q->front) % q->max] == x) // i : 맨 앞 요소로부터 몇번째 위치에 있는 값
			return i;		/* 검색 성공 */
	}
	return -1;				/* 검색 실패 */
}

/*--- 모든 데이터 출력 ---*/
void Print(const IntDequeue* q)
{
	int i;

	for (i = 0; i < q->num; i++)
		printf("%d ", q->que[(i + q->front) % q->max]);
	putchar('\n');
}

/*--- 큐의 종료 ---*/
void Terminate(IntDequeue* q)
{
	if (q->que != NULL)
		free(q->que);		/* 메모리에 할당한 배열 해제 */
	q->max = q->num = q->front = q->rear = 0;
}

구조체는 큐와 동일하고 큐에서 구현한 프로그램 Enque와 Deque에서 EnqueFront와 EqueRear, DequeFront와 DequeRear로 인큐와 디큐에 대해서 양방향으로 구현하는 함수를 만들어주면됩니다. 또한 Peek 함수도 양쪽 끝값들을 확인 할수 있도록 PeekFront와 PeekRear로 나누어줍니다. 나머지 함수는 큐에서 구현한 프로그램의 함수와 동일합니다.

• 맨 앞에 데이터 인큐하는 함수 : EnqueFront
  front가 배열의 시작 0이 되면 마지막 max값으로 번경해줍니다. max값은 인큐할 위치보다 1만큼 큰 값입니다. front값이 0이라면 front값을 max값으로 바꿔주어 EnqueRear와 겹치지 않게 해줍니다. front을 1만큼 감소시킨 후 기존의 덱의 첫번째 요소 앞에 값을 입력합니다.

• 맨 뒤에 데이터 인큐하는 함수 : EnqueRear
  기존의 큐를 구현할때 Enque(인큐)하는 함수와 같습니다. 큐는 맨 뒤의 데이터에 인큐하기 때문입니다.

• 맨 앞에서 데이터를 디큐 : DequeFront
  기존의 큐를 구현할때 Deque(디큐)하는 함수와 같습니다. 큐는 맨 앞의 데이터에 디큐하기 때문입니다.

• 맨 뒤에서 데이터를 디큐 : DequeRear
  rear값이 배열의 시작 0이 되면 마지막 max값으로 변경해줍니다.
  rear를 1만큼 감소시킨 후 기존의 덱의 마지막 요소를 버립니다.

• 맨 앞에서 데이터를 훔쳐보기 : PeekFront
  기존의 큐의 Peek 함수와 같이 맨 앞에서 데이터를 훔쳐봅니다.

• 맨 뒤에서 데이터를 훔쳐보기 : PeekRear
  기존의 큐와 같이 *x = q->que[q->rear -1]; 이라면 rear가 0일때 인덱스는 -1이 됩니다. *x = q->que[(q->rear - 1 + q->max) % q->max]로 하면 해결됩니다. 이와 같이 rear - 1에서 덱의 크기를 더해주고 덱의 크기의 나머지로 인텍스를 구현하면 해결됩니다.

아래는 IntDequeueTest.c 소스파일입니다.

/* int형 큐 IntDequeue를 사용하는 프로그램 */
#pragma warning (disable:4996)
#include <stdio.h>
#include "IntDequeue.h"

int main(void)
{
	IntDequeue que;

	if (Initialize(&que, 12) == -1) {
		puts("큐의 생성에 실패했습니다.");
		return 1;
	}

	while (1) {
		int m, x;
		int idx;

		printf("현재 데이터의 수 : %d / %d\n", Size(&que), Capacity(&que));
		printf("(1)맨 앞에 데이터 인큐 (2)맨 앞의 데이터 디큐 (3)맨 앞 피크 (4)출력\n"
			"(5)맨 뒤에 데이터 인큐 (6)맨 뒤의 데이터 디큐 (7)맨 뒤 피크 (8)검색\n"
			"(9)초기화 (10)비어 있는 상태 / 가득 찬 상태 (0)종료 : ");
		scanf("%d", &m);

		if (m == 0) break;

		switch (m) {
		case 1: /*--- 맨 앞에 데이터 인큐 ---*/
			printf("데이터：");   scanf("%d", &x);
			if (EnqueFront(&que, x) == -1)
				puts("\a오류 : 인큐에 실패했습니다.");
			break;

		case 2: /*--- 맨 앞의 데이터 디큐 ---*/
			if (DequeFront(&que, &x) == -1)
				puts("\a오류 : 디큐에 실패했습니다.");
			else
				printf("디큐한 데이터는 %d입니다.\n", x);
			break;

		case 3: /*--- 맨 앞 피크 ---*/
			if (PeekFront(&que, &x) == -1)
				puts("\a오류 : 피크에 실패했습니다.");
			else
				printf("피크한 데이터는 %d입니다.\n", x);
			break;

		case 4: /*--- 덱 출력 ---*/
			Print(&que);
			break;

		case 5: /*--- 맨 뒤에 데이터 인큐 ---*/
			printf("인큐：");   scanf("%d", &x);
			if (EnqueRear(&que, x) == -1)
				puts("\a오류 : 인큐에 실패했습니다.");
			break;

		case 6: /*--- 맨 뒤의 데이터 디큐 ---*/
			if (DequeRear(&que, &x) == -1)
				puts("\a오류 : 디큐에 실패했습니다.");
			else
				printf("디큐한 데이터는 %d입니다.\n", x);
			break;

		case 7: /*--- 맨 뒤 피크 ---*/
			if (PeekRear(&que, &x) == -1)
				puts("\a오류 : 피크에 실패했습니다.");
			else
				printf("피크한 데이터는 %d입니다.\n", x);
			break;

		case 8: /*--- 검색 ---*/
			printf("검색 데이터：");
			scanf("%d", &x);
			if ((idx = Search(&que, x)) == -1)
				puts("\a오류 : 검색에 실패했습니다.");
			else {
				printf("데이터는 인덱스 %d 위치에 있습니다.\n", idx);
				printf("큐의 맨 앞에서 %d만큼 뒤에 위치합니다.\n", Search2(&que, x));
			}
			break;

		case 9: /*--- 초기화 ---*/
			Clear(&que);
			break;

		case 10: /*--- 빈 상태 / 가득 찬 상태 판단 ---*/
			printf("큐가 비어 있%s.\n", IsEmpty(&que) ? "습니다" : "지 않습니다");
			printf("큐가 가득 %s.\n", IsFull(&que) ? "찼습니다" : "차지 않았습니다");
			break;
		}
	}

	Terminate(&que);

	return 0;
}