[자료구조] 파이썬의 deque - 양방향 큐, 원형 큐 구현
list가 [1,2,3,4,5]로 주어질 때, 배열의 끝에서 원소 추출하는 list.pop() 후에는 [1 ,2 ,3, 4]로 재정렬이 필요 없지만 (O(1)), 배열의 시작에서 추출하는 list.pop(0) 후에는 [2, 3, 4, 5]로 원소를 한 칸씩 옮겨주는 작업이 필요해, 시간 복잡도는 O(n)이 된다. list의 앞과 뒤 모두에서 원소의 추가와 삭제가 일어난다면, 이런 이유로 양방향 큐, 혹은 원형 큐를 사용하는 것이 더 이익이다. 파이썬에는 이를 이미 구현한 라이브러리가 있다. collections 모듈 - deque (Doubley-Ended Queue) deque는 덱이라고 읽으면 된단다. from collections import deque # declare queue queue = d..
2021. 2. 14.