[Python] deque

파이썬의 deque가 무엇인지 언제 사용해야 하는지 같이 알아보자. 🤔

 

보통 queue는 FIFO(First In First Out) 방식으로 작동한다. FIFO방식으로 작동하지 않는 양방향 queue가 존재하는데 그것이 바로 deque이다.

 

즉, 맨앞이나 맨뒤 양쪽 방향에서 원소를 추가하거나 제거할 수 있다. deque는 양 끝 원소의 append와 pop이 빠르다. 일반적인 List가 append와 pop연산에 O(n)이 소요되지만, deque O(1)으로 접근 가능하다.

deque에 존재하는 method는 아래와 같다.

 

- append(item) : 원소를 deque 오른쪽 끝에 삽입

- appendLeft(item) : 원소를 deque 왼쪽 끝에 삽입

- pop() : deque의 오른쪽 끝 원소를 가져오고 삭제

- popLeft() : deque의 왼쪽 끝 원소를 가져오고 삭제

- extend(array) : 주어진 배열을 순회하며 deque의 오른쪽에 추가

- extendLeft(array) : 주어진 배열을 순회하며 deque의 왼쪽에 추가

- remove(item) : 원소를 deque에서 찾아 삭제

 

deque는 stack처럼 사용할 수도 있고, queue처럼 사용할 수도 있다. 대부분의 경우에서 list보다 우수한 성능을 보여주며, append/pop 연산이 빈번한 경우 list와 비교해 월등한 성능을 보여준다.

 

참고 : https://leonkong.cc/posts/python-deque.html