먼저 들어간 데이터가 먼저 나오는 FIFO (First In First Out)의 성질을 가진 자료구조
특성
- 삭제 연산이 수행되는 곳을 front, 삽입연산이 수행되는 곳을 rear 라 한다.
- 요소는 rear로 들어와서 front로 빠진다. 접근은 가장 첫 원소와 끝 원소만 가능하다.
- rear에서 수행되는 삽입연산을 enQueue, front에서 수행되는 삭제연산을 deQueue라 한다.
- 시간복잡도
- 삽입/삭제 : O(1)
- 탐색 : O(n)
Queue 사용 with Python
# 데이터 흐름: 왼쪽방향
queue = [1, 2, 3]
# enQueue
queue.append(4) # queue = [1, 2, 3, 4]
# deQueue
queue.pop(0) # 1 반환, queue = [2, 3, 4]# 데이터흐름 : 오른쪽 방향
queue = [1, 2, 3]
# enQueue
queue.insert(0, 4) # queue = [4, 1, 2, 3]
# deQueue
queue.pop() # 3 반환, queue = [4, 1, 2]
Deque
python collections 모듈의 deque(double-ended queue)은 데이터를 양방향에서 추가/제거할 수 있는 자료구조
- list로 구현한 큐는 데이터가 메모리에 연속적으로 할당되어 있어 insert(0,.. ), pop(0) 등의 메서드를 수행할 때 데이터들의 메모리 위치를 전부 바꿔줘야 해서 O(1)의 시간복잡도가 아니다.
- deque은 linked list 로 이루어져 있기 때문에 popleft(), appendLeft() 메서드의 시간복잡도는 O(1)이다.
- linked list 의 속성으로 탐색의 시간복잡도가 O(n)이 걸린다.
- enQueue, deQueue 연산이 빈번히 일어나는 알고리즘에 사용한다.
from collections import deque
queue = deque([1, 2, 3]) # 초기화 deque(list)
print(queue) # deque([1, 2, 3])
### 왼쪽 방향
# enQueue
queue.append(4) # queue = [1, 2, 3, 4]
# deQueue
queue.popleft() # 1, queue = [2, 3, 4]
### 오른쪽 방향
# enQueue
queue.appendLeft(4) # queue = [4, 1, 2, 3]
# deQueue
queue.pop() # 3, queue = [1, 2, 3]728x90
