[Python] deque의 개념과 사용법, 장점

[Python] deque의 개념과 사용법, 장점

 

deque란?

양방향 큐(queue)로, 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다.

 

deque의 장점

양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다.

컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능하다.

 

deque 사용법

우선, 라이브러리 import 를 해줘야 한다.

from collections import deque

l = [1, 2, 3, 4]
d = deque(l)

 

리스트를 deque()의 입력으로 넣어주면 양방향 큐가 만들어진다.

 

길이가 정해진 deque 선언

기본적인 deque는 길이가 정해져 있지 않다.

고정된 길이를 정해주려면 선언 시 maxlen 인수를 추가하면 된다.

from colletions import deque

l = [1, 2, 3]
d = deque(l, maxlen=3)

 

deque의 내부 메소드

dir()명령어로 확인해보면 아래와 같은 내부 메소드들이 출력된다.

 

['__add__', '__bool__', '__class__', '__contains__', '__copy__', '__delattr__', '__delitem__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', 'append', 'appendleft', 'clear', 'copy', 'count', 'extend', 'extendleft', 'index', 'insert', 'maxlen', 'pop', 'popleft', 'remove', 'reverse', 'rotate']

 

리스트와 유사하지만, appendleft, popleft 함수들이 보인다.

이 것이 양방향 큐를 의미한다.

 

deque의 append

append 사용 시 일반 리스트와 동일하게 제일 마지막 인덱스에 원소가 추가된다.

leftappend는 제일 첫 번째 인덱스에 원소가 추가되며, pop에도 동일한 원리가 적용된다.

 

deque를 사용하는 이유

push/pop 연산이 빈번한 알고리즘에서 리스트보다 월등한 속도를 자랑하기 때문에 시간 효율성이 좋다.