덱(Deque)

Goal

• 덱을 구현 할 수 있다
• 덱의 구조를 그리고 설명할 수 있다

---

덱(Deque)

데이터의 입/출력이 양 끝단에서만 이루어지는 형태의 자료구조

 

덱

특징

• 원소의 추가 O(1)
• 원소의 삭제 O(1)
• 원소의 확인 O(1) - 제일 앞, 뒤쪽만 확인 가능
• 삽입 삭제가 양 끝단에서만 이루어지는 제한적 선형 자료구조이다

덱(Deque)은 앞, 뒤 양쪽에서 데이터의 삽입 삭제가 가능하다는 점에서 스택이나 큐보다 덜 제한적이다.

이런 특징 때문에 Deque을 Stack또는 Queue형태로 사용이 가능하다. (입출력 부분의 함수를 제한을 걸면된다)

덱(Deque)의 구현

BOJ 덱 구현 문제 : https://www.acmicpc.net/problem/10866

- 배열 덱 - https://github.com/jihyuk124/DataStructure/tree/master/03.Queue%2C%20Deque/ArrayDeque

- 연결 리스트 덱 - https://github.com/jihyuk124/DataStructure/tree/master/03.Queue%2C%20Deque/LinkedListDeque