Deque

📖Deque(Double-Ended Queue)

앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형

from collections import deque
 
dq = deque()
dq = deque('hello') # deque(['h', 'e', 'l', 'l', 'o'])

• 문자열을 이용해 deque를 만들면 각 문자를 값으로 가지는 리스트 형태의 deque가 만들어짐
• 큐를 구현해서 사용할 때, 리스트에 비해 속도가 굉장히 빠름

📖 삽입 함수

📎append(v)/appendleft(v)

가장 뒤/앞에 값을 추가하는 함수

from collections import deque
dq = deque('hello')
 
dq.append(v)
dq.appendleft(v)

📎insert(idx, v)

특정 인덱스에 값을 추가하는 함수

from collections import deque
dq = deque('hello')
 
dq.insert(idx, v)

📎extend(iterable)/extendleft(iterable)

iterable한 값을 하나씩 deque의 가장 뒤/앞에 추가하는 함수

from collections import deque
dq = deque('hello')
 
dq.extend(vs)
dq.extendleft(vs)

• iterable 값 자체가 들어가는 것이 아니라 iterable 안의 요소들이 각각의 값으로 들어감

📖삭제 함수

📎pop()/popleft()

가장 뒤/앞의 원소를 삭제한 후 return하는 함수

from collections import deque
dq = deque('hello')
 
dq.pop() # 'o'
dq.popleft() # 'h'

• 해당하는 값이 없으면 idxError 발생

📎remove(v)

제일 처음 나온 해당 값을 삭제하는 함수

from collections import deque
dq = deque('hello')
 
dq.remove('l') # dq(['h', 'e', 'l', 'o'])

• 해당하는 값이 없으면 valueError 발생

📖기타 함수

📎reverse()

deque의 순서를 반대로 뒤집는 함수

from collections import deque
dq = ('hello')
 
dq.reverse() # ['o', 'l', 'l', 'e', 'h']

• 리턴 값 없음

📎rotate(n)

deque를 n만큼 오른쪽으로 회전시키는 함수

from collections import deque
dq = ('hello')
 
dq.rotate(3) # ['l', 'l', 'o', 'h', 'e']

• n이 음수라면 왼쪽으로 회전
• 리턴 값 없음

📎clear()

deque에 있는 모든 원소를 제거하는 함수

from collections import deque
dq = ('hello')
 
dq.clear() # deque([])

📖시간복잡도

	list	deque
맨 앞 원소 추가	list.insert(0, v) O(n)	dq.appendleft() O(1)
맨 앞 원소 삭제	list.pop(0) O(n)	dq.popleft() O(1)
맨 뒷 원소 추가	list.append(v) O(1)	dq.append(v) O(1)
맨 뒷 원소 삭제	list.pop() O(1)	dq.pop() O(1)