collections - deque

참고 :

https://excelsior-cjh.tistory.com/96

collections 모듈 - deque

---

■ 정의 :

- double-ended queue 의 줄임말

- 양방향에서 데이터를 처리할 수 있는 queue형 자료구조를 의미

양 끝단에서 queue 작업만 할 경우 복잡도 O(1)

but list로 구현하면 pop(0), pop(-1)시 자료형에 기인하여 복잡도 O(N)

→  자료 입출력이 빈번하면 deque로 해결을 고려

 

■ 장점 

- 양 끝단 pop / insert 에 대해서 O(N)

import collections
import time
import datetime
# list

lst = ['a', 'b', 'c']
time_start_1 = time.monotonic()
lst.insert(0, 'd')
time_end_1 = time.monotonic()
elapse_time_1 = time_end_1 - time_start_1
print(f'datetime.timedelta(elapse_time_1) : {datetime.timedelta(elapse_time_1)}')
print(lst)

>>> 0:00:00.267389
>>> ['d', 'a', 'b', 'c']


# collections.deque
deq = collections.deque(['a', 'b', 'c'])
time_start_2 = time.monotonic()
deq.appendleft('d')
time_end_2 = time.monotonic()
elapse_time_2 = time_end_2 - time_start_2
print(f'datetime.timedelta(elapse_time_2) : {datetime.timedelta(elapse_time_2)}')
print(deq)

>>> 0:00:00.128565
>>> deque(['d', 'a', 'b', 'c'])

 

■ method들

1) append

(a) 정의 : 오른쪽 요소 삽입

    ex) list.append(x) 와 같음

import collections

deq = collections.deque(['a', 'b', 'c'])
deq.append('d')
print(deq)

>>> deque(['a', 'b', 'c', 'd'])

---

2) pop

(a) 정의 : 오른쪽 요소 제거

- list.pop( )과 같음, list.pop(0)는 왼쪽 pop 가능 →  deque는 popleft로 수행, pop(0) 없음

- 오른쪽(마지막)에서 부터 차례대로 제거와 반환(remove and return)

import collections

deq = collections.deque(['a', 'b', 'c'])

while deq:
    try:
        poped = deq.pop()
        print(poped, end='\n')
    except IndexError as e:
        print(f'error : {e}')
        break
>>>
c
b
a

---

3) appendleft

(a) 정의 : 왼쪽 요소 추가

import collections
deq = collections.deque(['a', 'b', 'c'])
deq.appendleft('d')
print(deq)

>>> deque(['d', 'a', 'b', 'c'])

---

4) popleft

(a) 정의 : 왼쪽 요소 제거

import collections
deq = collections.deque(['a', 'b', 'c'])
print('deque.popleft() ->', end=' ')
while True:
    try:
        print(deq.popleft(), end=' ')
    except IndexError:
        break

>>> deque.popleft() -> a b c

---

5) extend(iterable) / extendleft(iterable)

(a) 정의 : iterable을 deque 오른쪽 / 왼쪽에 연장 해주는 방식

    →  원소가 들어간다, iterable의 container가 원소로 가는게 아님

import collections
deq = collections.deque(['a', 'b', 'c'])
print(deq)
>>> deque(['a', 'b', 'c'])

deq.extendleft(['Hi', 'Python'])
print(deq)
>>> deque(['Python', 'Hi', 'a', 'b', 'c'])

deq.extend(['Goodbye', 'Python'])
print(deq)
>>> deque(['Python', 'Hi', 'a', 'b', 'c', 'Goodbye', 'Python'])

deq.extend('farewell')
print(deq)
>>> deque(['Python', 'Hi', 'a', 'b', 'c', 'Goodbye', 'Python', 
           'f', 'a', 'r', 'e', 'w', 'e', 'l', 'l'])