[ C언어 ] 자료구조_덱(연결 리스트_LinkedList)

1. 덱 자료구조 설명

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

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

 

2. 덱 자료구조 구현(연결 리스트)

연결 리스트를 사용해서 덱을 구현하는 방법도 스택과 덱을 구현한 방법과 동일합니다.

이전에 포스팅한 연결리스트(LinkedList)를 구현할 때 앞뒤에서 데이터를 삽입하는 기능을 이미 구현하였 기 때문에 이를 활용하기만 해도 구현이 가능합니다.

[ C언어 ] 자료구조_LinkedList

만약 연결 리스트 LinkedList를 모르시는 분은 위 블로그 URL로 들어가서 글을 봐주시기 바랍니다. 이미 알고 계시지만 코드가 없는 분들도 위 블로그에 코드를 만들어 놓았으니 복사해 주시기 바랍니다.

 

그럼 본격적으로 덱을 구현 해 보겠습니다.

덱을 구현하기 위해서는 LinkedList 를 구현할 때 만든 add_front(), add(), remove_front(), remove(), get() 함수를 사용할 것입니다.

 

그러면 덱을 구현할 함수를 먼저 정의해 보겠습니다.

 

Deque_LinkedList.h

typedef struct Deque Deque;

Deque* createDeque();

void destroyDeque(Deque*);

int deque_add_front(Deque* dq, int data);

int deque_add_rear(Deque* dq, int data);

int deque_delete_front(Deque* dq);

int deque_delete_rear(Deque* dq);

int deque_get_front(Deque* dq);

int deque_get_rear(Deque* dq);

int deque_isEmpty(Deque* dq);

 

여기서 typedef struct Deque Deque; 을 선언한 이유는 LinkedList의 함수를 사용하기 위해서는 LinkedList 해더파일을 include 해야 하는데 위 해더파일에서 선언하게 되면 main함수에서 Deque.h 를 선언함과 동시에 LinkedList.h 도 선언하게 돼버리기 때문에 Deque의 앞뒤에서만 입출력을 할 수 있도록 기능을 제한해야 하는데 LinkedList의 모든 함수를 사용할 수 있데 되면서 실수로 중간에 데이터를 삽입, 삭제해버리는 일이 생길 수 있습니다.

그래서 상단에 Deque 이라는 이름의 구조체가 있다는 것을 미리 알린 후 Deque의 기능만 사용하도록 제한하는 것입니다.

 

Deque_LinkedList.c

#include <stdlib.h>
#include "Deque_LinkedList.h"
#include "LinkedList.h"

struct Deque {
	LinkedList list;
};

Deque* createDeque()
{
	Deque* dq = malloc(sizeof(Deque));
	if (dq == NULL) return NULL;
	init(dq);
	return dq;
}

void destroyDeque(Deque* dq)
{
	while (size(&dq->list) > 0) remove_front(&dq->list);
	free(dq);
}

int deque_add_front(Deque* dq, int data)
{
	return add_front(&dq->list, data);
}

int deque_add_rear(Deque* dq, int data)
{
	return add(&dq->list, data);
}

int deque_delete_front(Deque* dq)
{
	return remove_front(&dq->list);
}

int deque_delete_rear(Deque* dq)
{
	return remove(&dq->list);
}

int deque_get_front(Deque* dq)
{
	return get(&dq->list, 0);
}

int deque_get_rear(Deque* dq)
{
	return get(&dq->list, dq->list.size);
}

int deque_isEmpty(Deque* dq)
{
	return size(&dq->list) == 0;
}

 

위 코드에서는 Deque.h 에서 정의한 함수를 실제로 구현하고 있습니다. 해더파일에서 정의하기만 한 Deque 구조체를 실제로 만들고 내부에 LinkedList를 타입으로 가지고 있습니다. 이렇게 Deque을 구현할 때는 LinkedList 에서 구현되어 있는 함수를 사용할 수 있도록 하였습니다.

중요한 것은 Deque을 사용하기 위해서는 메모리를 동적으로 할당받기 때문에 마지막에는 반듯이 할당받은 Deque 구조체의 메모리를 free로 해제해야 합니다.

 

main.c

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

void main()
{

	Deque* deque = createDeque();

	deque_add_front(deque, 2);
	deque_add_front(deque, 1);

	deque_add_rear(deque, 3);
	deque_add_rear(deque, 4);


	printf("[%d]", deque_get_front(deque));
	deque_delete_front(deque);

	printf("[%d]", deque_get_front(deque));
	deque_delete_front(deque);


	printf("[%d]", deque_get_rear(deque));
	deque_delete_rear(deque);

	printf("[%d]", deque_get_rear(deque));
	deque_delete_rear(deque);

	destroyDeque(deque);

	return 0;
}

 

이렇게 구현한 Deque_LinkedList.h 를 include 하면 Deque 기능만 사용할 수 있게 됩니다.

 

실행결과

 

이상으로 덱 자료구조를 LinkedList로 구현해 보았습니다.

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