[Python] deque의 정의, 함수, 활용 정리

1) Deque 정의

Deque는 "double-ended que"의 약자로 스택과 큐를 일반화 한 것이다.

 

List의 경우 고정 길이 연산에 특화되어 있으며, pop(0)과 insert(0, v) 연산에 대해 O(n)의 메모리 비용이 필요한 반면

Deque의 경우 추가(append)와  꺼내기(pop) 연산을 O(1)의 속도로 지원한다.

 

2) deque 함수들

3) deque 생성

from collections import deque

#deque 선언
queue = deque(['this', 'is', 'deque'])

print(queue) # deque(['this', 'is', 'deque'])

4) deque 활용하기

from collections import deque

#deque 생성
d = deque([1,2,3,2,4,7,2])

print("Find first occurence of 4")
print(d.index(4,0,5)) #인덱스 0~4 사이에 4를 찾아라
    
print("The count of 2 in deque is :")
print(d.count(2)) #2의 원소 갯수는?

print("after rotate")
d.rotate(2) #오른쪽으로 2번 회전
print(d)

print("reverse deque:")
print(deque(reversed(d)))

Find first occurence of 4
4
The count of 2 in deque is :
3
after rotate
deque([7, 2, 1, 2, 3, 2, 4])
reverse deque:
deque([4, 2, 3, 2, 1, 2, 7])
deque([7, 2, 1, 2, 3, 2, 4])