데크 사용법 복습
파이썬의 collections 모듈에서 제공하는 deque
(데크, double-ended queue)

양방향에서 요소를 추가하거나 제거할 수 있는 더 유연한 자료형

스택과 큐의 역할을 동시에 수행할 수 있음

from collections import deque
d = deque()

d.append('a')
d.appendleft('b')

d.pop()
d.popleft()

d.count('a')

d.extend(['x','y'])
d.extendleft(['x','y'])

d = deque(maxlen=3)

크기 제한을 초과하는 요소 추가를 할 시 오래된 요소가 삭제됨

d.clear()

d.insert(2,'x')

d.rotate(1)
d.rotate(-2)

양수는 오른쪽으로 회전

음수는 왼쪽으로 회전

d.reverse()

d = deque(my_list)
리스트와 데크의 비교
리스트는 구조적 변경이 느리지만 데이터 접근이 빠름
데크는 구조적 변경이 쉽지만 데이터 접근이 느림

데크의 각 기능별 리스트와의 속도비교
리스트가 데이터 접근 속도가 빠르다는 것을 제외하면
나머지는 데크보다 비슷하거나 느림

데크는 리스트와 동일한 시간 복잡도를 갖음

리스트는 인덱스 기반 접근이 가능하여
O(1)로 빠른 데이터 접근이 가능

데크은 인덱스를 통한 접근이 O(n)으로 느리므로,
리스트가 데이터 접근 속도에서 더 빠름

인덱스 기반 접근
데이터 구조에서
특정 요소에 접근하기 위해
그 요소의 위치를 나타내는 인덱스를 사용하여
직접적으로 해당 요소에 접근하는 방식

데크는 이중 연결 리스트로 구현되어 있어,
특정 인덱스의 요소에 접근할 때
모든 요소를 순회해야 할 수 있음
이로 인해 접근 시간 복잡도가 O(n)