큐는 FIFO(선입선출) 원칙을 따르는 데이터 구조입니다. (“파이썬 deque”가 queue의 일종)
사람들이 줄을 서서 기다리게 queue라고 생각하시면 됩니다. 먼저 도착한 사람이 가장 먼저 빠져나갑니다. 실제로 “queue”는 대기줄을 의미하는 단어입니다.
queue에서 요소는 후면(끝)에 추가되고 전면(전면)에서는 제거됩니다.
아래 그림을 확인해주세요.
큐 (Queue)는 언제 사용하는 걸까?
큐 자료구조의 특성에 맞게 시퀀스의 양쪽 끝에서 효율적인 삽입 및 삭제 작업이 중요한 시나리오에서 용이하게 쓰일 수 있습니다.
가령 예를 들면 아래와 같은 상황에서 쓰일 수 있겠죠?
- 작업 예약
- 네트워킹의 메시지 대기열
- 전자상거래 주문 처리
- 백그라운드 작업 처리
deque : 파이썬에서 큐
파이썬에서 deque를 사용합니다. deque는 양쪽 끝에서 삽입과 삭제를 허용하는 일반화된 큐 데이터 구조입니다.
큐 뿐만 아니라 스택으로도 사용할 수 있는 자료구조 입니다.
양쪽 끝에서 삽입 및 삭제에 대해 O(1) 시간 복잡도를 지원합니다.
파이썬 deque 의 장점
로테이션 작업
deque는 rotate 메서드를 제공하여 요소를 오른쪽이나 왼쪽으로 효율적으로 회전할 수 있습니다.
이는 순환 패턴이나 순환 버퍼를 구현해야 하는 시나리오에서 유용할 수 있습니다.
속도
deque를 반복하는 것은 일반적으로 리스트을 반복하는 것보다 빠르며, 특히 대규모 컬렉션과 관련된 시나리오의 경우 더욱 그렇습니다. 이는 반복 속도가 중요한 상황에서 유용할 수 있습니다.
파이썬 deque 모듈 가져오기
파이썬에서 deque를 사용하기 위해서는 collections 모듈을 사용합니다
from collections import dequedeque 생성
my_deque = deque() # 빈 deque 생성
my_deque2 = deque([1, 2, 3, 4, 5]) # 리스트를 받아서 deque생성요소 추가
# 오른쪽 끝에 요소 추가
my_deque.append(1)
my_deque.append(2)
print(my_deque) # deque([1, 2])
# 왼쪽 끝에 요소 추가
my_deque.appendleft(3)
my_deque.appendleft(4)
print(my_deque) # deque([4, 3, 1, 2])iterable 객체 추가
# 오른쪽에 iterable 객체를 순환하며 값들을 차례로 추가
my_deque.extend([7, 8, 9])
print(my_deque) # deque([4, 3, 1, 2, 7, 8, 9])
# 왼쪽에 iterable 객체를 순환하며 값들을 차례로 추가
my_deque.extendleft([2, 1, 0])
print(my_deque) # deque([0, 1, 2, 4, 3, 1, 2, 7, 8, 9])요소 제거
# 오른쪽 끝 요소 제거
popped_element = my_deque.pop()
print(popped_element) # Output: 9
# 왼쪽 끝 요소 제거
popped_left_element = my_deque.popleft()
print(popped_left_element) # Output: 0특정 요소 삭제
my_deque.remove(7)
my_deque.remove(8)
# my_deque.remove(9) # ValueError: 9 is not in deque
print(my_deque) # deque([1, 2, 4, 3, 1, 2])요소 접근하기
first_element = my_deque[0]
print(first_element) # Output: 1순환
n: 요소를 회전시키는 단계 수입니다. 양수 n은 오른쪽으로 회전하고, 음수 n은 왼쪽으로 회전합니다.
from collections import deque
my_deque = deque([1, 2, 3, 4, 5])
# Rotate to the right by 2 steps
my_deque.rotate(2)
print(my_deque)
# Output: deque([4, 5, 1, 2, 3])
# Rotate to the left by 3 steps
my_deque.rotate(-3)
print(my_deque)
# Output: deque([2, 3, 4, 5, 1])마치며
파이썬의 deque를 활용하면 백준의 실버 문제도 아주 손쉽게 풀리는 매직… 이미 구현된 자료구조는 꼭 활용해보는 게 좋은 것 같습니다 ㅎㅎ
참고하면 좋은 글
deque in Python | Pythontic.com
Queue Introduction | PrepInsta