덱 (Deque)
삽입과 삭제가 양쪽 끝에서 모두 발생할 수 있는 자료구조
큐의 장점과 스택의 장점을 합쳐놓은 자료구조이다.
특징
크기가 가변적
중간요소가 삽입, 삭제될 때 , 요소들을 앞/ 뒤로 밀 수 있으므로 vector보다 좋은 성능을 가짐
앞/뒤 삽입 삭제 성능은 좋지만 중간의 삽입/삭제 성능은 좋지 않음
시간복잡도
삽입/삭제 : 원소를 앞,뒤에 삽입하는 경우 : O(1)
탐색 : 원소를 탐색하는 경우 O(1) 인덱스 접근
단점
중간에서 삽입 삭제가 어려움
구현이 어려움
'자료구조' 카테고리의 다른 글
| 다익스트라 알고리즘 (Dijkstra Algorithm) (0) | 2021.05.07 |
|---|---|
| 그래프 (Graph), 인접 행렬, 인접 리스트 (0) | 2021.05.07 |
| 우선순위 큐 (Prioity Queue) (0) | 2021.05.06 |
| 큐 (Queue), 선형 큐, 원형 큐 (0) | 2021.05.06 |
| 스택 (Stack) (0) | 2021.05.06 |