[자료구조] Deque

Deque?

Deque(덱)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조 입니다.

 

두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있으며, 큐와 스택을 합친 형태로 생각할 수 있습니다.

 

deque는 양방향으로 삽입삭제를 할 수 있기 때문에 단방향으로만 삽입 삭제가 이루어지는 queue와 stack에 비해 삽입 삭제를 좀 더 간편하게 할 수 있습니다.

 

삽입과 삭제시 O(1)로 굉장히 빠르지만 deque 중간에 있는 데이터에는 접근하기 어렵다는 단점이 있습니다.

Deque의 구현

Deque는 최소한 다음과 기능을 수행할 수 있도록 구현했습니다.

• create : deque를 생성
• insertFront : deque의 맨앞에 원소를 추가
• deleteFront : deque의 맨앞의 원소를 빼냄
• peekFront : deque의 맨앞의 원소를 가져옴(deque에서 제거하지 않음)
• insertRear : deque의 맨 뒤에 원소를 추가
• deleteRear : deque의 맨 뒤에 원소를 빼냄
• peekRear : deque의 맨 뒤의 원소를 가져옴(deque에서 제거하지 않음)
• isEmpty : deque의 원소가 비어있는지 확인합니다.
• delete : deque를 삭제합니다.

deque같은 경우 확장성과 양 끝의 접근이 간편한 링크드 리스트를 이용하여 구현하였습니다.

https://github.com/zxcv9203/dataStructure/blob/master/chap04/linkeddeque.c

GitHub - zxcv9203/dataStructure