[자료구조] 덱(Deque)

2022. 4. 10. 23:10· 자료구조

 

양방향으로 넣고 뺄수 있는 자료구조

deque : double ended queue

[양방향 연결리스트를 기반으로 구현된 덱] 

 

<특징>

양방향 연결리스트를 이용하여 만들며, head와 tail을 각각 가리킨다

 

▶ ADT 

필요한 기능 : 덱 초기화, 덱 비었는지 확인, 덱의 머리/꼬리에 데이터 저장, 덱의 머리/꼬리에 데이터를 반환 및 소멸, 

덱의 머리/꼬리에 있는 데이터를 소멸하지 않고 반환

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

 

▶ 구현

 

  • 덱를 의미하는 구조체 (head와 tail이 있다)
typedef struct _dlDeque
{
	Node * head;
	Node * tail;
} DLDeque;

 

  • ADT의 구현
void DequeInit(Deque * pdeq)
{
	pdeq->head = NULL;
	pdeq->tail = 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; //덱 비어 있으면 pdeq->head는 null임

	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; //덱 비어 있으면 pdeq->tail은 null임

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

 

<특징>

DQAddFirst/Last → 야무지게 코드가 짜져있음

 

'자료구조' 카테고리의 다른 글

[자료구조] 우선순위 큐(Priority Queue)와 힙(Heap)  (0) 2022.04.24
[자료구조] 트리(Tree)  (0) 2022.04.17
[자료구조] 큐(Queue)  (0) 2022.04.10
[자료구조] 스택 (Stack)  (0) 2022.04.02
[자료구조] 연결 리스트 (Linked list)  (0) 2022.04.01
'자료구조' 카테고리의 다른 글
  • [자료구조] 우선순위 큐(Priority Queue)와 힙(Heap)
  • [자료구조] 트리(Tree)
  • [자료구조] 큐(Queue)
  • [자료구조] 스택 (Stack)
생선묵김치찌개
생선묵김치찌개
생선묵김치찌개
준혁's 코딩 연구기록
생선묵김치찌개
전체
오늘
어제
  • 분류 전체보기 (96)
    • Java (5)
    • Spring Boot (3)
    • 자료구조 (8)
    • 네트워크 (4)
    • 데이터베이스 (4)
    • 기술적 고민 (17)
      • Side Match (13)
      • 자리나따 (4)
    • C++ (3)
    • Algorithm (4)
    • PS 연습 (38)
    • 잡동사니 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • sentry
  • 트리
  • 예외처리
  • Stream
  • 재귀
  • 알고리즘
  • 큐
  • backend
  • 수식트리
  • 스프링
  • 원형 연결 리스트
  • 완전탐색
  • 브루트 포스
  • ㄱ
  • 단순 연결 리스트
  • 백준 골드
  • CPP
  • 해커톤
  • 양방향 연결 리스트
  • 자료구조
  • 이진트리
  • DN
  • 배열 리스트
  • aws rds
  • dp
  • 스택
  • 백준
  • 파일 업로드
  • open api
  • 열혈 자료구조

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
생선묵김치찌개
[자료구조] 덱(Deque)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.