[ C언어 ] 자료구조_덱(배열_Array)

1. 덱 자료구조 설명

덱 은 이전에 알아본 스택과 큐를 결합한 형태의 자료구조입니다.

앞뒤로 데이터를 넣을 수도 있고 꺼낼 수도 있습니다.

 

2. 덱 자료구조 구현(배열)

덱은 이전에 포스팅한 원향큐에 조금만 코드를 추가하면 됩니다.

[ C언어 ] 자료구조_큐(Array)

위에서는 rear 쪽에서 삽입하고 frount 쪽에서 삭제를 하였지만 반대방향으로도 동작할 수 있도록 바꿔주기만 하면 됩니다.

*이번 덱 자료구조는 위 코드와는 달리 조금 수정해서 새로 구현하였습니다*

 

Deque_Array.h

typedef int element;
#define DEQUE_SIZE 10
typedef struct Deque {
	element data[DEQUE_SIZE + 1];
	int frount;
	int rear;
}Deque;

int init(Deque* dq);

int frount_add(Deque* dq, element data);

int rear_add(Deque* dq, element data);

element frount_remove(Deque* dq);

element rear_remove(Deque* dq);

int size(Deque* dq);

void deque_print(Deque* dq);

 

원형큐 는 공백상태와 포화상태를 구분하기 위해 index 하나의 공간은 비워야 한다고 위 블로그에서 말했습니다.

그래서 실제 size 는 10이 아닌 9 이기 때문에 이번 덱 자료구조를 구현할 때는 10 + 1을 하여 실제 데이터를 담을 수 있는 공간을 10으로 만들었습니다.

이 부분을 유의하시면서 이후 코드를 봐주세요!

 

Deque_Array.c

#include "Deque_Array.h"

int is_empty(Deque* dq)
{
	return dq->frount == dq->rear;
}

int is_full(Deque* dq)
{
	return ((dq->rear + 1) % (DEQUE_SIZE + 1)) == dq->frount;
}

int init(Deque* dq)
{
	dq->frount = 0;
	dq->rear = 0;
	return 0;
}

int frount_add(Deque* dq, element data)
{
	if (is_full(dq)) return 1;

	dq->data[dq->frount] = data;
	dq->frount = (dq->frount + DEQUE_SIZE) % (DEQUE_SIZE + 1);

	return 0;
}

int rear_add(Deque* dq, element data)
{
	if (is_full(dq)) return 1;

	dq->rear = (dq->rear + 1) % (DEQUE_SIZE + 1);

	dq->data[dq->rear] = data;

	return 0;
}

element frount_remove(Deque* dq)
{
	if (is_empty(dq))
	{
		exit(1);
	}

	dq->frount = (dq->frount + 1) % (DEQUE_SIZE + 1);

	return dq->data[dq->frount];

}

element rear_remove(Deque* dq)
{
	if (is_empty(dq))
	{
		exit(1);
	}

	element save = dq->data[dq->rear];
	dq->rear = (dq->rear + DEQUE_SIZE) % (DEQUE_SIZE + 1);

	return save;
}

int size(Deque* dq)
{
	return dq->rear - dq->frount;
}

void deque_print(Deque* dq)
{
	int i = dq->frount;

	while (i != dq->rear)
	{
		i = (i + 1) % (DEQUE_SIZE + 1);
		printf("[%d] ", dq->data[i]);
	}
	printf("\n");
}

 

 

main.c

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

int main()
{
	Deque deque;

	init(&deque);

	frount_add(&deque, 1);
	deque_print(&deque);

	frount_add(&deque, 2);
	deque_print(&deque);

	rear_add(&deque, 3);
	deque_print(&deque);

	rear_add(&deque, 4);
	deque_print(&deque);


	printf("삭제 [%d]\n", rear_remove(&deque));
	deque_print(&deque);
	printf("삭제 [%d]\n", rear_remove(&deque));
	deque_print(&deque);
	printf("삭제 [%d]\n", rear_remove(&deque));
	deque_print(&deque);
	printf("삭제 [%d]\n", rear_remove(&deque));
	deque_print(&deque);
    
	return 0;
}

 

실행결과

 

이상으로 배열을 사용하여 자료구조 덱을 구현 해 보았습니다.

끝까지 글을 읽어주셔서 감사합니다.