Python - deque objects

https://docs.python.org/3/library/collections.html#collections.deque

collections — Container datatypes — Python 3.10.0 documentation

---

deque

iterable 객체이다.

처음 선언해 줄 때, 값을 지정해주지 않으면 비어있는 객체가 반환된다.

 

Deque는 "deck"이라고 발음하고, "double-ended queue"의 약자이다.

stack처럼 사용할 수도 있고, queue처럼 사용할 수도 있다.

어느 방향에서든 거의 동일한 O(1) 성능으로, deque의 양쪽에서 thread-safe하게 메모리 효율적인 append와 pop을 지원한다.

 

list object에서 비슷한 연산을 지원하지만, 빠른 fixes-length(고정 길이)에 최적화 되어 있고 pop과 insert 같은 길이와 원소들의 위치가 변하는 연산에 O(n)만큼의 비용이 발생한다.

 

MAXLEN을 지정하지 않았거나 None이면, deque는 임의의 길이로 성장할 수 있다.

MAXLEN을 지정했다면 deque는 지정된 최대 길이로 제한된다.

제한된 길이의 deque가 가득 차면, 새 원소를 추가할 때 맨 앞 원소가 삭제된다.

728x90

관련 method & 사용법

>>> from collections import deque

>>> d = deque('ghi')

 

append & appendleft

>>> d
deque(['g', 'h', 'i'])

>>> d.append('j')		# 오른쪽에 삽입
>>> d.appendleft('f') 	# 왼쪽에 삽입

>>> d
deque(['f', 'g', 'h', 'i', 'j'])

 

pop & popleft

>>> d
deque(['f', 'g', 'h', 'i', 'j'])

>>> d.pop()		# 가장 오른쪽 원소 return and remove
'j'
>>> d.popleft()	# 가장 왼쪽 원소 return and remove
'f'

>>> d
deque(['g', 'h', 'i'])

 

list로 변환 가능

>>> d
deque(['g', 'h', 'i'])

>>> list(d)
['g', 'h', 'i']

 

index 접근 방법

>>> d
deque(['g', 'h', 'i'])

>>> d[0]
'g'
>>> d[-1]
'i'

 

reversed

>>> d
deque(['g', 'h', 'i'])

>>> list(reversed(d)) 	# 원소의 순서를 뒤집은 list
['i', 'h', 'g']
>>> deque(reversed(d)) 	# 원소의 순서를 뒤집은 새로운 deque
deque(['i', 'h', 'g'])

>>> d					# 기존의 deque엔 영향을 주지 않는다.
deque(['g', 'h', 'i'])

 

in

>>> d
deque(['g', 'h', 'i'])

>>> 'h' in d  # deque 안에 해당 원소가 있는지 확인
True

 

extend & extendleft

>>> d
deque(['g', 'h', 'i'])

>>> d.extend('jkl') # 오른쪽에 하나씩 추가
deque(['g', 'h', 'i', 'j', 'k', 'l'])

>>> d.extendleft('abc') # 왼쪽에 하나씩 순서대로 추가
deque(['c', 'b', 'a', 'g', 'h', 'i', 'j', 'k', 'l'])

 

rotate

>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])

>>> d.rotate(1)		# 오른쪽으로 한칸씩
>>> d
deque(['l', 'g', 'h', 'i', 'j', 'k'])

>>> d.rotate(-1)	# 왼쪽으로 한칸씩
>>> d
deque(['g', 'h', 'i', 'j', 'k', 'l'])

 

clear

>>> d.clear()                        # deque를 비운다
>>> d.pop()                          # deque가 비어 있기 때문에 error 발생
Traceback (most recent call last):
    File "<pyshell#6>", line 1, in -toplevel-
        d.pop()
IndexError: pop from an empty deque