프로그래밍/파이썬

[Python] deque 사용하기

파이썬에서 큐(queue) 자료구조를 사용하는 방법은 list 사용하기 deque 사용하기 Queue 클래스 사용하기 등이 있다. 그중 deque에 대해 자세히 알아보려고 한다. deque deque는 collections 모듈에서 사용할 수 있다. deque는 “double-ended queue”의 약자이며, 스택과 큐를 일반화한 것으로, 양방향에서 원소를 추가하고 제거할 수 있는 자료구조이다. 양쪽 끝에서의 추가와 제거를 O(1) 성능으로 지원한다. deque는 내부적으로 linked list를 사용하고 있어 무작위로 접근할 경우 O(n) 시간 복잡도를 가진다. deque가 지원하는 메서드는 다음과 같다. append(x) 데크의 오른쪽에 x를 추가합니다. appendleft(x) 데크의 왼쪽에 x를..