덱은 큐와 스택의 성질을 동시에 가지고 있는 자료구조로, 양쪽 끝에서 삽입과 삭제가 전부 가능한 Restricted Structure이다. C++ STL에서는 deque<>로 사용 가능하다.
덱의 성질
- 원소의 추가가 O(1)
- 원소의 제거가 O(1)
- 제일 앞,뒤 원소의 확인이 O(1)
- 제일 앞,뒤 원소를 제외한 나머지 원소들의 확인,변경이 원칙적으로 불가능
-> STL deque에서는 인덱스로 나머지 원소들에 접근이 가능하긴 하다.
이 때문에 STL deque와 STL vector는 비슷한 성질을 지니고 있는데, 차이점이 몇 가지 존재한다.
- deque는 원소들이 여러 메모리 블록에 흩어져 있는 반면에 vector는 모든 원소가 하나의 메모리 블록에 연속적으로 할당되어 있다. 따라서 인덱스로 접근하는 속도가 같은 O(1)이긴 하지만 vector가 deque보다 더 빠르다.
- 맨 앞 원소의 추가,삭제에 대해 deque는 O(1)이지만, vector는 모든 원소를 1칸씩 옮겨야 하므로 O(N)의 시간 복잡도가 걸린다. 따라서 이는 deque의 큰 장점이다.
STL deque의 멤버 함수
- deque 선언
- deque<변수 타입> 이름
- deque 접근
- deque.front(): 덱의 맨 앞 원소를 반환한다.
- deque.back(): 덱의 맨 뒤 원소를 반환한다.
- deque 삽입/삭제
- push_front(element): 덱의 맨 앞에 원소를 삽입한다.
- push_back(element): 덱의 맨 뒤에 원소를 삽입한다.
- pop_front(): 덱의 맨 앞 원소를 제거한다.
- pop_back(): 덱의 맨 뒤 원소를 제거한다.
- deque 정보
- empty(): 덱이 비어있으면 1, 아니면 0을 반환한다.
- size(): 덱의 원소의 개수를 반환한다.
