개요
예전에 Python에서 큐를 다루는 방법을 소개하고자 2021.10.07 - [자료 구조] 회문 찾기 / 큐 & 스택을 작성했었는데, 찾아보니 deque라는 자료구조가 따로 존재해 내용을 적어둔다.
양방향 큐 (deque)
Queue는 먼저 저장한 자료를 먼저 빼내는 선입선출(First In First Out; FIFO) 방식의 자료구조다. REAR에서민 자료를 추가하고 FRONT에서만 자료를 삭제하기 때문에 방향을 구분하지 않는다.
반면 양방향 큐(Double-Ended Queue; deque)는 그 이름대로 데이터의 추가와 삭제가 FRONT, REAR 모두에서 이뤄진다. 즉, FIFO나 후입선출(Last In First Out; LIFO)를 따르지 않는다.
Deque는 기본적으로 동적 배열을 사용하고, Queue에 비해 시간 및 자원 활용 측면에서 효율적이다. 또한 자료구조 내 요소에 대한 임의 접근이 가능하다는 특징이 있다.
Deque 특징
- 크기가 가변적이다.
- FRONT, REAR에서의 데이터 추가, 삭제하기 좋은 반면 자료 구조 중간에 데이터를 추가하고 삭제하는 작업은 용이하지 않다.
- 임의 접근이 가능하다.
Queue VS Deque
큐와 양방향 큐를 비교하면 다음과 같다.
| Queue | Deque |
| REAR에서 자료를 추가하고, FRONT에서 자료를 삭제하는 선형 데이터 구조 | 양쪽 끝에서 자료를 추가하고 제거하는 선형 데이터 구조 |
| 선입선출 | 선입선출, 후입선출 모두 가능 |
| Array 또는 Linked List로 구현 | Circular Array 또는 Doubly Linked List로 구현 |
| 우선순위 큐나 우선순위 스택을 구현하는데 사용 | 양방향 우선순위 큐나 순환 버퍼를 구현하는데 사용 |
| enqueue, dequeue, peek, size 등의 기능 제공 | addFirst, addLast, RemoveFirst, RemoveLast, peekFirst, peekLast 등의 기능 제공 |
| iterator를 사용한 접근 미제공 | iterator를 사용한 접근 제공 |
| BFS(Breadth-First Search), 레벨 별 이진트리 인쇄 등이 알고리즘 예시가 될 수 있다. | 슬라이딩 윈도우, 슬라이딩 윈도우의 최대/최솟값 유지 등이 알고리즘 예시가 될 수 있다. |
참고 문서
https://www.geeksforgeeks.org/difference-between-queue-and-deque-queue-vs-deque/