[자료구조] 덱 Deque(Double-ended-queue) 큐 구현

덱 Deque(Double-ended-queue)

덱(deque)은 double-ended queue의 줄임말로써 후단(rear)으로만 데이터를 삽입했던 기존 선형 큐, 원형 큐와 달리 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐입니다. 

 

덱에 사용되는 Abstract Data Type

 ▪ create() ::= 덱을 생성한다.

 ▪ init(dq) ::= 덱을 초기화한다.

 ▪ is_empty(dq) ::=   덱이 공백상태인지를 검사한다.

 ▪ is_full(dq) ::= 덱이 포화상태인지를 검사한다.

 ▪ add_front(dq, e) ::= 덱의 앞에 요소를 추가한다.

 ▪ add_rear(dq, e) ::= 덱의 뒤에 요소를 추가한다.

 ▪ delete_front(dq) ::= 덱의 앞에 있는 요소를 반환한 다음 삭제한다 

 ▪ delete_rear(dq) ::= 덱의 뒤에 있는 요소를 반환한 다음 삭제한다.

 ▪ get_front(q) ::= 덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환한다.

 ▪ get_rear(q) ::= 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소를 반환한다.

 

덱의 연산에서 주의할 점은 데이터를 삽입 연산 시 front는 감소하고 rear는 증가하며 삭제 연산 시 front는 증가하고 rear는 감소하는 점입니다.

 

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct {  // 덱 큐 타입
	element  data[MAX_QUEUE_SIZE];
	int  front, rear;
} DequeType;
// 오류 함수
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}
// 덱 초기화 
void init_deque(DequeType *q)
{
	q->front = q->rear =  0;
}
// 공백 상태 검출 함수
int is_empty(DequeType *q)
{
	return (  q->front == q->rear );
}
// 포화 상태 검출 함수
int is_full(DequeType *q)
{
	return (( q->rear  + 1) % MAX_QUEUE_SIZE == q->front);
}
// 덱 큐 출력 함수
void deque_print(DequeType *q)
{
	printf("DEQUE(front=%d rear=%d) = ", q->front, q->rear);
	if (!is_empty(q)) {
		int i = q->front; // i에 현재 q의 front값을 넣어주고
		do {
			i = (i + 1) % (MAX_QUEUE_SIZE); // i의 자리를 1증가
			printf("%d | ", q->data[i]); // 증가한 i 자리에 해당하는 data값을 출력
		} while ( i != q->rear); 
	}
	printf("\n");
}
// rear쪽 삽입 함수
void add_rear(DequeType *q, element item)
{
	if (is_full(q))
		error("큐가 포화상태입니다");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE; // rear값 1 증가
	q->data[ q->rear ] = item;
}
// rear쪽 삭제 함수
element delete_rear(DequeType *q)
{
	int prev = q->rear;
	if (is_empty(q))
		error("큐가 공백상태입니다");
	q->rear =  (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE; // rear값 1감소
	return q->data[prev];
}
// rear쪽 반환
element get_rear(DequeType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	return q->data[ q->rear ];
}
// front쪽 삽입 함수
void add_front(DequeType *q, element val)
{
	if (is_full(q))
		error("큐가 포화상태입니다");
	q->data[ q->front ] = val;
	q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE; // front값 1감소
} 
// front쪽 삭제 함수
element delete_front(DequeType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	q->front =  (q->front + 1) % MAX_QUEUE_SIZE  ; // front값 1 증가
	return q->data[ q->front ];
}
// front쪽 반환
element get_front(DequeType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	return q->data[ (q->front + 1) % MAX_QUEUE_SIZE ];
}
// 메인
int main(void)
{
	DequeType queue;

	init_deque(&queue);
	for (int i = 0; i < 3; i++) {
		add_front(&queue, i);
		deque_print(&queue);
	}
	for (int i = 0; i < 3; i++) {
		delete_rear(&queue);
		deque_print(&queue);
	}
	return 0;
}

/* 실행결과
DEQUE(front=4 rear=0) = 0 |
DEQUE(front=3 rear=0) = 1 | 0 |
DEQUE(front=2 rear=0) = 2 | 1 | 0 |
DEQUE(front=2 rear=4) = 2 | 1 |
DEQUE(front=2 rear=3) = 2 |
DEQUE(front=2 rear=2) =
*/

 

 

이제 덱을 활용한 문제를 알아봅시다

Palindrome 검사 프로그램

주어진 문자열을 모두 덱에 삽입한 후, 앞과 뒤에서 뽑아 같은지 확인을 반복하여 회문 여부를 출력하시오.

int palindrome_check(DequeType* q) {
	while (!is_empty(q)) {
		if (delete_front(q) != delete_rear(q)) {
			return 0;
		}
		else {
			return 1;
		}	
	}
	return 1;
}

int main()
{
	printf("단어 입력 : ");
	DequeType dq;
	char str[30];
	gets_s(str, 30);
	init_deque(&dq);
	for (int i = 0; i < strlen(str); i++) {
		add_rear(&dq, str[i]);
	}
	if (palindrome_check(&dq)) {
		printf("회문입니다");
	}
	else {
		printf("회문이 아닙니다");
	}
	return 0;
}

기존의 덱을 구현하는 소스코드에서 정수형이 아닌 char형 문자열의 회문을 검사해야 하므로 element를 int로 지정한 부분을 char로 수정합니다. 이외 ADT연산 함수들은 모두 동일합니다.

 

회문 검사 함수 : 매개변수로 덱 타입 포인터 q를 받습니다. 덱 q의 데이터가 남아있는 한 계속 반복하는 반복문 while에서 만약 q의 front에서 잘라낸 데이터와 q의 rear에서 잘라낸 데이터가 같지 않을 경우 (즉, 남아있는 문자열의 앞 뒤가 다를 경우) 거짓임을 의미하는 0을 출력합니다.

 

그게 아닌 모든 경우(즉, q의 front에서 잘라낸 데이터와 q의 rear에서 잘라낸 데이터가 같은 경우, 또는 잘라냈는데 문자가 1개 남은 경우)에는 참임을 의미하는 1을 출력합니다

 

메인 함수 : 덱 타입 dq를 선언하고 입력할 문자 배열을 담을 char배열 str을 30의 공간을 설정하여 선언합니다. gets_s() 함수로 str과 공간30을 넘겨 문자열을 입력받을 수 있도록 하고 dq를 초기화합니다.

i는 0부터 str의 길이의 전 까지 1씩 증가하는 반복문 for에서 add_rear()를 통해 dq의 rear에 str 문자배열의 문자들을 하나씩 모두 삽입합니다.

 

이후 회문 검사 함수로 해당 덱 dq를 넣어 회문인지 아닌지를 판별합니다