먼저 큐라는 개념이 필요한데 큐는 선입선출(FIFO)의 자료구조라고 할 수 있다. Queue 라고도 하는데, Queue라는 단어 자체가 표 같은 것을 구매하기 위해 줄서는 것을 의미한다.
데이터가 들어오는 위치는 가장 뒤에 있고, 데이터가 나가는 위치는 가장 앞에 있어서, 먼저 들어오는 데이터가 먼저 나가게 된다.
이러한 큐를 양방향으로 쓸 수 있게 만든 자료구조가 데크(deque)이다.
deque 특징
- 큐를 양방향으로 쓸 수 있게 만든 자료 구조
- 양 끝 element에 대해서 append와 pop 가능
- 스택과 큐를 동시에 사용 가능
무엇보다 데크를 사용해야 하는 이유는 속도에 있다.
리스트는 O(n)인데 데크는 O(1)이고 각각 n번씩 반복하면 리스트 구현은 O(n^2)지만 데크 구현은 O(n) 성능의 차이가 굉장히 크다.
deque 사용법
from collections import deque
queue = deque()
queue.append('A')
queue.append('B')
queue.append('C')
print( queue ) # deque(['A', 'B', 'C'])
print( queue[0] ) # A
element = queue.popleft()
print( element, queue ) # A deque(['B', 'C'])
element = queue.popleft()
print( element, queue ) # B deque(['C'])
element = queue.popleft()
print( element, queue ) # C deque([])
참고 사이트:
반응형
