Python Queue 구현 방법

Queue는 이미 대학교에서 배웠구, 이미 잘 알고 있는 내용이지만, 그때의 나는 이미 알고리즘을 안 써 본지 너무 오래되기도 했구... 코테를 공부하고 있는 시점이니. 다시 큐에 대해서 정리하는 방법을 적어본다.

Queue란?

• Queue는 기본적으로 선입선출되는 자료구조이다. 그렇기에 'FIFO (First in, First out)방식으로 작동한다. 즉, 먼저 들어가서 먼저 나간다는 점이다.

기본 개념

• Enqueue: 큐의 뒤쪽에 요소를 추가하는 작업.
• Dequeue: 큐의 앞쪽에서 요소를 제거하는 작업.
• Peek: 큐의 앞쪽에 있는 요소를 확인하지만 제거하지 않는 작업.
• Is Empty: 큐가 비어 있는지 확인하는 작업.

특징

• BFS(너비 우선 탐색): 그래프 탐색 알고리즘에서 사용되어 각 노드를 탐색하는 순서를 관리합니다.

큐의 종류

• 일반 큐 (Simple Queue): 기본적인 FIFO 구조.
• 원형 큐 (Circular Queue): 큐의 끝이 처음으로 연결되어 있어 공간을 효율적으로 사용하는 구조.
• 우선순위 큐 (Priority Queue): 각 요소에 우선순위를 부여하여, 높은 우선순위를 가진 요소가 먼저 제거되는 구조.
• 이중 큐 (Deque): 양쪽에서 요소를 추가하거나 제거할 수 있는 큐.

이렇게 간단하게 알아보았다.

출처

• 뤼튼

파이썬 구현 방법

from collections import deque

# 큐 생성
queue = deque()

# 큐에 요소 추가
queue.append(1)
queue.append(2)
queue.append(3)

# 큐에서 요소 제거 (FIFO)
print(queue.popleft())  # 출력: 1
print(queue)  # 출력: deque([2, 3])

deque를 사용하는 이유는 list를 사용할 경우, 앞의 데이터를 모두 앞으로 끌어와야 하고 그렇게 할 경우 시간 복잡도가 늘어나기 때문에 collections 라이브러리를 사용하는 게 더 효율적입니다.

또한 쓰는 이유는

1. 효율적인 성능
   O(1) 시간 복잡도: deque는 양쪽 끝에서의 삽입과 삭제가 O(1) 시간 복잡도로 수행됩니다. 이는 리스트의 경우, 앞쪽에서 요소를 제거할 때 O(n)의 시간 복잡도가 걸리는 것과 대조적입니다. 따라서 큐(First In First Out)나 스택(Last In First Out)으로 사용할 때 성능이 뛰어납니다.
2. 양방향 접근
   양쪽 끝에서의 작업: deque는 양쪽 끝에서 요소를 추가하거나 제거할 수 있습니다. 즉, 큐로 사용할 때는 앞에서 제거하고 뒤에서 추가하는 것이 가능하며, 스택으로 사용할 때는 뒤에서만 작업할 수 있습니다.
3. 유연성
   다양한 활용: deque는 큐와 스택 이외에도 다양한 알고리즘이나 데이터 구조를 구현하는 데 사용할 수 있습니다. 예를 들어, 슬라이딩 윈도우 알고리즘, BFS(너비 우선 탐색) 등에서 유용하게 사용됩니다.
4. 내장 기능
   기본적인 메서드 제공: deque는 append(), popleft(), appendleft(), pop() 등의 메서드를 제공하여 큐와 스택을 쉽게 구현하고 사용할 수 있게 해줍니다.

다음과 같은 이유가 있습니다.