deque

• 덱 자료구조를 구현한 클래스.
• 스택과 큐의 일반화된 형태. 양끝에서의 삽입과 삭제 연산에 O(1)의 성능을 보장한다.

사용방식

deque([iterable[,maxlen]])

• 기존의 iterable을 가지고 deque로 만들 수 있다.
• maxlen을 지정하지 않으면 임의의 길이로 커질 수 있다.
• maxlen을 지정한뒤 덱이 가득 찬 이후의 입력은 반대편을 하나씩 밀어내며 삽입된다.

from collections import deque

dq = [1,2,3,4]
dq = deque(dq,maxlen = 5)
print(dq)
#deque([1, 2, 3, 4], maxlen=5)

append(x)

• 오른쪽에 x 추가

appendleft(x)

• 왼쪽에 x 추가

dq.append(5)
dq.appendleft(6)
#maxlen 이상을 삽입하므로 반대쪽의 5가 삭제
print(dq)
#deque([6, 1, 2, 3, 4], maxlen=5)

clear()

• 모든 요소를 제거하고 길이가 0인 상태로 만듦.

copy()

• 얕은 복사

count(x)

• 덱에서 x의 개수를 셈

extend(iterable)

• 오른쪽으로 iterable 확장

extendleft(iterable)

• 왼쪽으로 iterable 확장.
• iterable을 뒤집은 형태로 붙는다는 점을 주의

ex = [5,6,7,8]
dq.extend(ex)
print(dq)
#deque([4, 5, 6, 7, 8])

ex = [1,2,3,4]
dq.extend(ex)
print(dq)
#deque([4, 3, 2, 1, 4])
#역순으로 붙음.

index(x[,start[,stop]])

• x의 index를 start~stop 사이에서 처음 나오는 위치를 찾음. 찾지못하면 ValueError

insert(i,x)

• x를 i 위치에 삽입. 이때 i가 maxlen보다 크면 IndexError

pop()

• 오른쪽에서 하나를 꺼냄. 비어 있으면 IndexError

popleft()

• 왼쪽에서 하나를 꺼냄. 비어 있으면 IndexError

remove(value)

• 처음 나오는 value를 제거. 찾을 수 없으면 ValueError

reverse()

• 덱의 순서를 뒤집고 None 반환

rotate(n=1)

• n 만큼 오른쪽으로 회전. 음수면 왼쪽으로 회전.

maxlen

• 덱의 최대 크기. 제한이 없으면 None 반환.

기타

• 리스트처럼 index로 접근 가능
• 길이를 n으로 제한한 deque는 iterable의 마지막 n개 원소를 가져오는 유닉스의 tail 처럼 사용 할 수 있음.
• deque를 통해 최근 n개에 대한 통계자료 등을 유지할 수 있음.
• round robin scheduler를 구현하는데 사용 가능
• rotate 함수를 사용하여 스택 조작을 구현할 수 있음.