BFS(너비 우선 탐색 알고리즘)에서 큐 자료구조를 쓸 때 'deque' 이라는 단어가 자주 나와서 궁금해졌다.
[WHAT IS❓] deque
큐 자료구조에 대해 공부하다보면 'duque 라이브러리'를 쓰게 되는데 이때 'deque'이란 정확히 뭘까 하는 사람들이 많을 것이다.
먼저 큐(queue) 자료구조 방식은 선입선출(FIFO : 먼저 들어온게 먼저 나감) 방식으로 작동하는 반면, 덱(deque) 은 '앞'과 '뒤' 즉, 양쪽 방향에서 값을 추가하거나 삭제할 수 있다.
그렇기 때문에 양쪽에서의 pop과 append 연산을 빠르게 할 수 있다.
deque 라이브러리
deque는 라이브러리를 임포트 시켜 사용할 수 있는데 이 라이브러리에서 사용할 수 있는데 메서드는 대략적으로 다음과 같다.
- deque.append(item) : item을 deque의 오른쪽 끝에 삽입한다.
- deque.appendleft(item) : item을 deque의 왼쪽 끝에 삽입한다.
- deque.pop() : deque의 오른쪽 끝 엘리먼트를 가져오는 동시에 deque에서 삭제한다.
- deque.popleft() : deque의 왼쪽 끝 엘리먼트를 가져오는 동시에 deque에서 삭제한다.
- deque.extend(array) : 주어진 배열(array)을 순환하면서 deque의 오른쪽에 추가한다.
- deque.extendleft(array) : 주어진 배열(array)을 순환하면서 deque의 왼쪽에 추가한다.
- deque.remove(item) : item을 deque에서 찾아 삭제한다.
- deque.rotate(num) : deque를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).