#14 덱(Deque)의 이해와 구현

Deque

double-ended queue를 줄여서 표현한 것.

앞으로도 뒤로도 데이터를 넣을 수 있고, 앞으로도 뒤로도 데이터를 뺄수 있는 자료구조를 말한다.

 

ADT

* void DequeInit(Deque * pdeq);
- 덱의 초기화를 진행한다.
- 덱 생성 후 제일 먼저 호출되어야 하는 함수이다.

* int DQIsEmpty(Deque * pdeq);
- 덱이 빈 경우 TRUE(1)를, 그렇지 않은 경우 FALSE(0)을 반환한다.

* void DQAddFirst(Deque * pdeq, Data data);
- 덱의 머리에 데이터를 저장한다. data로 전달된 값을 저장한다.

* void DQAddLast(Deque * pdeq, Data data);
- 덱의 꼬리에 데이터를 저장한다. data로 전달된 값을 저장한다.

* Data DQRemoveFirst(Deque * pdeq);
- 덱의 머리에 위치한 데이터를 반환 및 소멸한다.

* Data DQRemoveLast(Deque * pdeq);
- 덱의 꼬리에 위치한 데이터를 반환 및 소멸한다.

* Data DGGetFirst(Deque * pdeq);
- 덱의 머리에 위치한 데이터를 소멸하지 않고 반환한다.

* Data DQGetLast(Deque * pdeq);
- 덱의 꼬리에 위치한 데이터를 소멸하지 않고 반환한다.

 

main.c

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

int main(void)
{
	// Deque의 생성 및 초기화
	Deque deq;
	DequeInit(&deq);

	// 데이터 넣기 1차
	DQAddFirst(&deq, 3);
	DQAddFirst(&deq, 2);
	DQAddFirst(&deq, 1);

	DQAddLast(&deq, 4);
	DQAddLast(&deq, 5);
	DQAddLast(&deq, 6);

	// 데이터 꺼내기 1차
	while (!DQIsEmpty(&deq))
		printf("%d ", DQRemoveFirst(&deq));

	printf("\n");

	// 데이터 넣기 2차
	DQAddFirst(&deq, 3);
	DQAddFirst(&deq, 2);
	DQAddFirst(&deq, 1);

	DQAddLast(&deq, 4);
	DQAddLast(&deq, 5);
	DQAddLast(&deq, 6);

	// 데이터 꺼내기 2차
	while (!DQIsEmpty(&deq))
		printf("%d ", DQRemoveLast(&deq));

	return 0;
}

 

Deque.h

#ifndef __DEQUE_H__
#define __DEQUE_H__

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node* next;
	struct _node* prev;
} Node;

typedef struct _dlDeque
{
	Node* head;
	Node* tail;
} DLDeque;

typedef DLDeque Deque;

void DequeInit(Deque* pdeq);
int DQIsEmpty(Deque* pdeq);

void DQAddFirst(Deque* pdeq, Data data); // 덱의 머리에 데이터 추가
void DQAddLast(Deque* pdeq, Data data); // 덱의 꼬리에 데이터 추가

Data DQRemoveFirst(Deque* pdeq); // 덱의 머리에서 데이터 삭제
Data DQRemoveLast(Deque* pdeq); // 덱의 꼬리에서 데이터 삭제

Data DQGetFirst(Deque* pdeq); // 덱의 머리에서 데이터 참조
Data DQGetLast(Deque* pdeq); // 덱의 꼬리에서 데이터 참조

#endif

 

Deque.c

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

void DequeInit(Deque* pdeq)
{
	pdeq->head = NULL;
	pdeq->tail = NULL;
}

int DQIsEmpty(Deque* pdeq)
{
	if (pdeq->head == NULL) // head가 NULL이면 비어있는 덱!
		return TRUE;
	else
		return FALSE;
}

void DQAddFirst(Deque* pdeq, Data data) // 덱의 머리에 데이터 추가
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = pdeq->head;

	if (DQIsEmpty(pdeq))
		pdeq->tail = newNode;
	else
		pdeq->head->prev = newNode;

	newNode->prev = NULL;
	pdeq->head = newNode;
}

void DQAddLast(Deque* pdeq, Data data) // 덱의 꼬리에 데이터 추가
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->prev = pdeq->tail;

	if (DQIsEmpty(pdeq))
		pdeq->head = newNode;
	else
		pdeq->tail->next = newNode;

	newNode->next = NULL;
	pdeq->tail = newNode;
}

Data DQRemoveFirst(Deque* pdeq) // 덱의 머리에서 데이터 삭제
{
	Node* rnode = pdeq->head;
	Data rdata;
	if (DQIsEmpty(pdeq)) { printf("Deque Memory Error!"); exit(-1); }
	rdata = pdeq->head->data;

	pdeq->head = pdeq->head->next;
	free(rnode);

	if (pdeq->head == NULL)
		pdeq->tail = NULL;
	else
		pdeq->head->prev = NULL;

	return rdata;
}

Data DQRemoveLast(Deque* pdeq) // 덱의 꼬리에서 데이터 삭제
{
	Node* rnode = pdeq->tail;
	Data rdata;
	if (DQIsEmpty(pdeq)) { printf("Deque Memory Error!"); exit(-1); }
	rdata = pdeq->tail->data;

	pdeq->tail = pdeq->tail->prev;
	free(rnode);

	if (pdeq->tail == NULL)
		pdeq->head = NULL;
	else
		pdeq->tail->next = NULL;

	return rdata;
}

Data DQGetFirst(Deque* pdeq) // 덱의 머리에서 데이터 참조
{
	if (DQIsEmpty(pdeq)) { printf("Deque Memory Error!"); exit(-1); }

	return pdeq->head->data;
}

Data DQGetLast(Deque* pdeq) // 덱의 꼬리에서 데이터 참조
{
	if (DQIsEmpty(pdeq)) { printf("Deque Memory Error!"); exit(-1); }

	return pdeq->tail->data;
}