덱(Double-Ended Queue, Deque)은 양방향 대기열이라고도 불리는 자료구조이다. 외형적으로는 queue와 비슷한 구조를 갖고있으며, 한 방향인 queue와 stack과는 다르게 LIFO, FIFO같은 순서에 구속되지 않는다.
즉, 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능하며 어떤 쪽으로 입력하고 출력하느냐에 따라서 stack과 queue로 사용할 수 있다. 이때, 한쪽으로만 입력이 가능하도록 설정한 덱을 스크롤(scroll)이라고 하고 한쪽으로만 출력이 가능하도록 설정한 덱을 셸프(shelf)라고 한다.
특징
덱은 다음과 같은 특징을 갖고 있다.
- Stack 및 Queue를 모두 사용할 수 있다.
덱은 양쪽으로 데이터를 추가하고 삭제할 수 있기 때문에 둘 다 구현이 가능하다. 만약 양쪽 다 삭제가 가능하고 왼쪽에서만 추가가 가능하게 구현한다면 왼쪽으로 삭제하는 형태는 stack과 같고 오른쪽으로 삭제하는 형태는 queue와 같아진다.
마찬가지로, 양쪽 다 추가가 가능하고 오른쪽에서만 삭제가 가능하게 구현한다면 왼쪽에서는 queue와 같고 오른쪽에서는 stack과 같은 형태를 갖게 된다.
이렇게 추가와 삭제의 기능을 제한해서 상황에 맞는 자료구조를 구현할 수 있다. - 연속 메모리 공간이 아니다.
- 양방향 끝에서 데이터 추가, 삭제가 용이하다.
- 양방향 끝이 아닌 임의의 데이터만 추가하거나 삭제하는 것은 불가능하다.
'개발 일지 > CS' 카테고리의 다른 글
[알고리즘] 이진 탐색 알고리즘(Binary Search Algorithm) (0) | 2023.01.19 |
---|---|
[알고리즘] 완전 탐색 알고리즘(Brute-Force Algorithm, BFA) (0) | 2023.01.19 |
[알고리즘] 탐욕 알고리즘(Greedy Algorithm) (0) | 2023.01.19 |
[알고리즘] 시간 복잡도(Time Complexity) (0) | 2023.01.19 |
[알고리즘] 너비 우선 탐색(BFS) / 깊이 우선 탐색(DFS) (0) | 2023.01.17 |