Ch 7 - 2 덱

(1) 덱의 이해

Deque(덱)을 디큐라고 읽지 않는 이유 : 큐의 기초연산 디큐와 햇갈릴 수 있기 때문

스텍 : 입구와 출구가 같다.
큐 : 입구와 출구가 양쪽 끝이다.

덱 : Double(Double ended queue)
양쪽으로 넣을 수 있고 양쪽 방향으로 꺼낼 수 있는 큐가 바로 덱이다.

(어제 백준에서 Circular queue를 공부하고 https://www.acmicpc.net/problem/1021 회전하는 큐를 풀어봤는데 알고리즘에'덱'이라 적혀있었다. 그 이유를 몰랐는데 이제 알겠다.)

덱은 스텍과 큐의 특성을 모두 가지고 있는 자료구조라고도 하는데
한쪽만 쓰면 스텍과 같이, 한쪽을 입구, 한쪽을 출구로만 쓰면 큐와 같이 쓸 수 있다.
그러나 이 설명에는 논란이 있는데 두개의 입출구를 가지고 있어서 스텍과 큐처럼 쓸 수 있는 것이지 스텍과 큐의 특성을 모두 가지고 있다고 이야기할 수는 없다고도 한다.

덱의 연산 -
앞으로 넣기, 앞에서 빼기, 뒤로 넣기, 뒤에서 빼기

(2) 나의 구현

강의에서 제공된 헤더 파일

#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

내가 구현한 소스 파일

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

void DequeInit(Deque* pdeq)
{
	pdeq->head = (Node*)malloc(sizeof(Node));
	pdeq->tail = (Node*)malloc(sizeof(Node));
	pdeq->head->next = pdeq->tail;
	pdeq->tail->prev = pdeq->head;
}

int DQIsEmpty(Deque* pdeq)
{
	if (pdeq->head->next == pdeq->tail) return 1;
	else return 0;
}

void DQAddFirst(Deque* pdeq, Data data)
{
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->data = data;
	temp->next = pdeq->head->next;
	pdeq->head->next->prev = temp;
	pdeq->head->next = temp;
	temp->prev = pdeq->head;
}

void DQAddLast(Deque* pdeq, Data data)
{
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->data = data;
	temp->prev = pdeq->tail->prev;
	pdeq->tail->prev->next = temp;
	pdeq->tail->prev = temp;
	temp->next = pdeq->tail;
}

Data DQRemoveFirst(Deque* pdeq)
{
	if (DQIsEmpty(pdeq))
	{
		printf("덱이 굶어죽어요\n");
		exit(-1);
	}
	else
	{
		Node* delNode = pdeq->head->next;
		Data delData = pdeq->head->next->data;
		pdeq->head->next = delNode->next;
		delNode->next->prev = pdeq->head;
		free(delNode);
		return delData;
	}
}

Data DQRemoveLast(Deque* pdeq)
{
	if (DQIsEmpty(pdeq))
	{
		printf("덱이 굶어죽어요\n");
		exit(-1);
	}
	else
	{
		Node* delNode = pdeq->tail->prev;
		Data delData = pdeq->tail->prev->data;
		pdeq->tail->prev = delNode->prev;
		delNode->prev->next = pdeq->tail;
		free(delNode);
		return delData;
	}
}

Data DQGetFirst(Deque* pdeq)
{
	if (DQIsEmpty(pdeq))
	{
		printf("덱이 굶어죽어요\n");
		exit(-1);
	}
	else return pdeq->head->next->data;
}

Data DQGetLast(Deque* pdeq)
{
	if (DQIsEmpty(pdeq))
	{
		printf("덱이 굶어죽어요\n");
		exit(-1);
	}
	else return pdeq->tail->prev->data;
}

(3) 강의에서 구현한 소스파일

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

void DequeInit(Deque * pdeq)
{
	pdeq->head = NULL;
	pdeq->tail = NULL;
}//아 이건 나랑 아예 다르네. 나는 더미 노드를 만들고, 강의에서는 NULL로 시작

int DQIsEmpty(Deque * pdeq)
{
	if(pdeq->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 = pdeq->head->data;

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

	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 = pdeq->tail->data;

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

	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;
}