큐(Queue)는 컴퓨터 과학에서 중요한 자료 구조 중 하나로, 데이터의 삽입과 삭제가 "가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 자료구조" 입니다.
다른 말로 FIFO(First-In, First-Out) 방식으로 이루어지는 구조를 말합니다.
현실 세계와 대응시켜보면, 대기열과 개념과 유사해요.
예를 들어, 은행 또는 도넛가게에서 줄을 서게 되면, 먼저 온 사람의 업무를 처리하거나 음식을 주고 나가게 되거든요.
이는 큐의 작동 방식과 비슷합니다.
큐의 주요 특징
1. FIFO 구조: 가장 먼저 삽입된 데이터가 가장 먼저 삭제됩니다.
2. 두 개의 주요 연산:
- Enqueue: 큐의 끝에 새로운 데이터를 추가하는 연산.
- Dequeue: 큐의 앞에서 데이터를 제거하는 연산.
3. 전형적인 큐 연산:
- enqueue(item): 큐의 끝에 `item`을 추가합니다.
- dequeue(): 큐의 앞에서 데이터를 제거하고 반환합니다.
- peek() 또는 front(): 큐의 앞에 있는 데이터를 제거하지 않고 반환합니다.
- is_empty(): 큐가 비어있는지를 확인합니다.
- size(): 큐의 크기(현재 큐에 있는 데이터의 수)를 반환합니다.
큐의 구현 방법
큐는 배열 또는 연결 리스트를 사용하여 구현할 수 있습니다. 각 방법은 고유한 장단점을 가지고 있습니다.
1. 배열 기반 구현:
- 고정된 크기를 갖는 배열을 사용하여 구현할 수 있습니다.
- 단점: 크기가 고정되어 있어 초기 크기 설정이 중요합니다.
- 원형 큐(Circular Queue): 배열의 끝과 시작을 연결하여 공간을 효율적으로 사용합니다.
2. 연결 리스트 기반 구현:
- 노드의 동적 할당을 통해 크기의 제한 없이 큐를 구현할 수 있습니다.
- 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함합니다.
- 연결 리스트를 사용하면 메모리의 동적 관리를 통해 공간을 효율적으로 사용할 수 있습니다.
파이썬에서는 `collections` 모듈의 `deque` 클래스 또는 `queue` 모듈을 사용하여 큐를 쉽게 구현할 수 있습니다.
## 1. `collections.deque` 사용
from collections import deque
# 큐 생성
queue = deque()
# 데이터 삽입
queue.append('A')
queue.append('B')
queue.append('C')
# 데이터 삭제
print(queue.popleft()) # A
print(queue.popleft()) # B
# 큐의 현재 상태
print(queue) # deque(['C'])
2. `queue.Queue` 사용:
from queue import Queue
# 큐 생성
queue = Queue()
# 데이터 삽입
queue.put('A')
queue.put('B')
queue.put('C')
# 데이터 삭제
print(queue.get()) # A
print(queue.get()) # B
# 큐의 현재 상태 확인
print(queue.qsize()) # 1 (남은 아이템의 수)
큐는 많은 실생활 응용 프로그램에서 중요하게 사용됩니다.
예를 들어, 프린터 작업 대기열, 프로세스 관리, 네트워크 패킷 처리 등 다양한 분야에서 사용됩니다.
이를 통해 데이터의 순차적 처리 및 관리가 효율적으로 이루어질 수 있습니다.
이와 비슷한 개념으로는 Stack 이 있는데요
Stack 은 Queue와는 다르게 "가장 마지막에 삽입된 데이터가 가장 먼저 삭제되는 자료구조" 입니다.
다른 말로 LIFO(Last-In, First-Out) 방식으로 이루어지는 구조를 말합니다.