Deque: Double Ended Queue(덱)
양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조
큐와 스택을 합친 형태로도 생각 가능
Deque의 연산
push_front(item)
- item 하나를 덱의 맨 앞부분에 추가
push_end(item)
- item 하나를 덱의 맨 뒷부분에 추가
pop_front()
- 덱의 맨 앞부분의 item을 제거
pop_end()
- 덱의 맨 뒷부분의 item을 제거
front()
- 덱의 맨 앞부분의 item을 반환
rear()
- 덱의 맨 뒷부분의 item을 반환
isEmpty()
- 덱이 비어있다면 True를 반환하고 비어있지 않다면 False를 반환
size()
- 덱의 size를 반환
시간복잡도
Search(검색)
- 특정 데이터를 찾을 때는 순차적으로 접근하여 찾으므로 시간복잡도 O(n)
Insert(삽입)
- 덱은 맨 앞과 맨 뒤에 데이터를 삽입하므로 시간복잡도 O(1)
deletion(삭제)
- 덱은 맨 앞과 맨 뒤의 데이터를 삭제하므로 시간복잡도 O(1)
