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