-
[Python] DequeProgramming/Python 2023. 6. 3. 15:55728x90
list를 이용해서 queue처럼 사용할 수 있습니다.
queue = [1, 2, 3] queue.append(4) #[1, 2, 3, 4] queue.pop(0) #[2, 3, 4] queue.insert(0, 5) #[5, 2, 3, 4]
하지만 list를 queue처럼 사용하는 것은 성능 측면에서 추천되지 않습니다.
list는 Random Access에 최적화된 자료구조이기 때문에 pop(0), insert(0, x)는 성능적으로 매우 불리한 연산입니다.
이 연산의 시간 복잡도는 O(n)입니다.
Deque
collections 모듈의 deque를 사용해서 queue, stack 자료구조를 구현할 수 있습니다.
collections에 queue도 있지만 Deque가 훨씬 빠르니 코딩테스트에서는 Deque를 사용하는 것이 좋습니다.
method
append(item) item을 deque의 맨 뒤(오른쪽 끝)에 삽입한다. appendleft(item) item을 deque의 맾 앞(왼쪽 끝)에 삽입한다. pop() deque의 오른쪽 끝 element를 가져오는 동시에 deque에서 삭제한다. popleft() deque의 왼쪽 끝 element를 가져오는 동시에 deque에서 삭제한다. extend(array) 주어진 배열(array)를 순환하면서 deque의 오른쪽에 추가한다. extendleft(array) 주어진 배열(array)를 순환하면서 deque의 왼쪽에 추가한다. remove(item) item을 deque에서 찾아 삭제한다. rotate(num) deque를 num만큼 회전한다.(양수 : 오른쪽, 음수 : 왼쪽) example
from collections import deque n = 3 m = 4 queue = deque([1,2,3,4,5]) queue.rotate(1) #deque([5, 1, 2, 3, 4]) queue.rotate(-1) #deque([1, 2, 3, 4, 5]) queue.remove(4) #deque([1, 2, 3, 5]) arr = [8, 7, 9] queue.extend(arr) #deque([1, 2, 3, 5, 8, 7, 9]) arr = [11, 12, 10] queue.extendleft(arr) #deque([10, 12, 11, 1, 2, 3, 5, 8, 7, 9]) #arr앞에서 부터 deque앞에 추가한다.
Queue
from collections import deque queue = deque([1, 2]) queue.append(3) #deque([1, 2, 3]) queue.append(4) #deque([1, 2, 3, 4]) a = queue.popleft() # a = 1 # deque([2, 3, 4]) b = queue.popleft() # b = 2 # deque([3, 4])
Stack
from collections import deque queue = deque([1, 2]) queue.appendleft(3) #deque([3, 1, 2]) queue.appendleft(4) #deque([4, 3, 1, 2]) a = queue.popleft() # a = 4 # deque([3, 1, 2]) b = queue.popleft() # b = 3 #deque([1, 2])
728x90'Programming > Python' 카테고리의 다른 글
[Python] 리스트 컴프리헨션 List Comprehension (0) 2023.06.03 [python] poetry install , 설정 (0) 2023.04.28 [Python] 기본 데이터 구조 (0) 2023.03.06 [Python] 파이썬 순열과 조합 (0) 2022.05.17 [Python] 파이썬 자주 사용되는 라이브러리 (0) 2022.05.17