반응형
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;
}
반응형