열혈 자료구조 - 7-4 덱(Deque)의 이해와 구현

덱(Deque)의 이해

- Double ended queue의 줄임말

- 큐는 rear나 front 한쪽 방향으로 넣고 꺼내는 자료구조

- 덱은 양쪽 방향으로 넣거나 꺼낼 수 있는 자료구조

- 자료구조는 덱이라고 읽고 꺼내는 ADT는 디큐라고 읽음

 

 

- 넣은 쪽으로만 넣고 꺼내면 스택처럼 사용 가능

- 넣은 쪽과 꺼낸 쪽을 다르게 하면 큐처럼 사용 가능

 

덱의 구현

- 덱을 구현하는 데는 양방향 연결 리스트가 가장 적합

- 단순 연결 리스트로 구현했을 때는 Tail쪽 삭제를 위해서는 Tail의 앞쪽 노드를 가르키는 노드 포인터가 따로 필요하기 때문

- 구조체 정의

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

typedef struct _dlDeque
{
	Node * head;		// 앞쪽을 가르키는 노드 포인터
	Node * tail;		// 뒤쪽을 가르키는 노드 포인터
} DLDeque;

- 앞으로 넣기

void DQAddFirst(Deque * pdeq, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = pdeq->head;		// new node의 next가 현재 head

	if(DQIsEmpty(pdeq))
		pdeq->tail = newNode;		// 첫 삽입이었다면 tail도 new node
	else
		pdeq->head->prev = newNode;

	newNode->prev = NULL;
	pdeq->head = newNode;			// head는 new node
}

- 앞에서 빼기

Data DQRemoveFirst(Deque * pdeq)
{
	Node * rnode = pdeq->head;			// 현재 head를 따로 저장
	Data rdata = pdeq->head->data;

	if(DQIsEmpty(pdeq))
	{
		printf("Deque Memory Error!");
		exit(-1);
	}

	pdeq->head = pdeq->head->next;		// 현재 head의 다음 노드를 head로 교체
	free(rnode);						// head였던 노드 삭제

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

	return rdata;
}

- 뒤로 넣기

void DQAddLast(Deque * pdeq, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->prev = pdeq->tail;		// new node의 이전을 tail로 설정

	if(DQIsEmpty(pdeq))
		pdeq->head = newNode;		// 첫 노드라면 head도 됨
	else
		pdeq->tail->next = newNode;		

	newNode->next = NULL;
	pdeq->tail = newNode;			// new node가 tail이 됨
}

- 뒤에서 빼기

Data DQRemoveLast(Deque * pdeq)
{
	Node * rnode = pdeq->tail;			// 현재 tail 따로 저장
	Data rdata = pdeq->tail->data;

	if(DQIsEmpty(pdeq))
	{
		printf("Deque Memory Error!");
		exit(-1);
	}

	pdeq->tail = pdeq->tail->prev;		// 현재 tail의 이전 노드가 tail이 됨
	free(rnode);						// tail 이었던 노드 삭제

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

	return rdata;
}