큐
큐(Queue)는 컴퓨터 과학에서 자주 사용하는 중요한 자료구조 중 하나로, 항목들이 'FIFO'(First-In, First-Out, 선입선출) 순서로 추가되고 제거되는 특징을 가지고 있다. 이는 실생활에서 줄을 서는 것과 비슷한 개념으로 생각할 수 있다. 줄의 첫 번째에 서 있는 사람이 먼저 서비스를 받고, 그 다음으로 줄에 선 사람이 서비스를 받는 식이다.
큐에는 두 가지 주요 연산이 있다.
- Enqueue: 항목을 큐의 뒤쪽에 추가합니다.
- Dequeue: 큐의 앞쪽에서 항목을 제거하고 반환합니다.
이 외에도, 큐의 앞쪽에 무엇이 있는지 확인하는 'Peek'나 'Front' 연산, 큐가 비어 있는지 확인하는 'IsEmpty' 연산 등이 있을 수 있다.
큐는 다양한 컴퓨팅 문제를 해결하는 데 사용된다. 예를 들어, 컴퓨터의 태스크 스케줄링, 네트워크 프린터의 인쇄 작업 관리, 너비 우선 탐색(Breadth-First Search) 등에 사용된다.
또한, '우선순위 큐(Priority Queue)', '원형 큐(Circular Queue)', '덱(Deque, Double Ended Queue)' 등과 같은 다양한 변형 형태의 큐도 존재한다.
Enqueue, Dequeue
Enqueue와 Dequeue는 큐 자료구조의 두 가지 주요 연산이다.
Enqueue: Enqueue는 항목을 큐의 끝(일반적으로 'rear' 또는 'back'이라고 불림)에 추가하는 연산이다. 새로운 항목은 항상 큐의 끝에 추가되므로, 이전에 큐에 들어온 항목들은 뒤로 밀려난다. 이 연산이 수행된 후에는, 새롭게 추가된 항목이 큐의 맨 끝에 위치하게 된다.
Dequeue: Dequeue는 큐의 시작(일반적으로 'front' 또는 'head'라고 불림)에서 항목을 제거하고, 그 항목을 반환하는 연산이다. Dequeue 연산이 수행되면, 가장 먼저 큐에 추가된 항목이 제거되고, 그 다음으로 추가된 항목이 큐의 시작 위치로 이동한다. 큐가 비어 있을 때 Dequeue 연산을 시도하면, 에러나 예외 상황을 반환하거나, 특정 값(예: null)을 반환하도록 정의할 수 있다.
Enqueue와 Dequeue 연산은 큐가 'FIFO'(First-In, First-Out) 구조를 유지하도록 보장한다. 즉, 가장 먼저 큐에 추가된 항목이 가장 먼저 제거되는 구조를 가진다. 이러한 성질 덕분에 큐는 여러 분야에서 실시간 처리, 스케줄링, 버퍼링 등 다양한 용도로 사용된다.
파이썬의 'queue' 모듈
import queue
# 큐 생성
q = queue.Queue()
# 큐에 데이터 삽입 (Enqueue)
q.put("apple")
q.put("banana")
q.put("cherry")
# 큐에서 데이터 꺼내기 (Dequeue)
first_item = q.get()
print(first_item) # "apple" 출력
second_item = q.get()
print(second_item) # "banana" 출력
# 큐가 비어 있는지 확인
if q.empty():
print("Queue is empty")
else:
print("Queue is not empty")위의 코드에서 queue.Queue()를 호출하여 큐를 생성하였고, put 메서드를 사용하여 큐에 항목을 추가(Enqueue)하였다. 그리고 get 메서드를 사용하여 큐에서 항목을 제거(Dequeue)하였다. empty 메서드는 큐가 비어 있는지를 확인해준다.
이렇게 파이썬의 queue 모듈은 기본적인 큐 연산을 쉽게 사용할 수 있도록 해준다. 또한, 이 모듈은 스레드 간의 안전한 통신을 위해 설계되었으므로, 멀티스레딩 환경에서도 사용할 수 있다.
참고로, 파이썬에서 리스트를 사용하여 간단한 큐를 구현할 수도 있지만, 큐의 길이가 길어질수록 리스트를 사용한 Enqueue(list.append)와 Dequeue(list.pop(0)) 연산의 효율성이 떨어진다. 이러한 경우에는 collections.deque 자료구조를 사용하는 것이 좋다. deque는 양쪽 끝에서의 삽입과 제거가 O(1) 시간 복잡도로 이루어진다.
Queue(), LifoQueue(), PriorityQueue()
파이썬의 queue 모듈은 다양한 종류의 큐를 제공한다: Queue(), LifoQueue(), PriorityQueue() 등이 그 예이다. 이들은 각각 다음과 같은 특징을 가지고 있다.
- Queue(): 가장 기본적인 큐 자료구조로, FIFO(First-In, First-Out) 정책을 따릅니다. 가장 먼저 큐에 들어간 항목이 가장 먼저 나오게 됩니다. 이는 실생활에서 사람들이 줄을 서서 기다리는 것과 비슷하다.
- LifoQueue(): LIFO(Last-In, First-Out) 정책을 따르는 스택 구현이다. 가장 나중에 큐에 들어간 항목이 가장 먼저 나오게 된다. 이는 책을 쌓아 놓은 더미에서 맨 위에 있는 책을 먼저 가져가는 것과 비슷하다.
- PriorityQueue(): 각 항목에 우선순위가 부여되어 있고, 우선순위가 높은 항목이 먼저 dequeue되는 큐이다. 항목은 튜플로 제공되며, 첫 번째 원소는 우선순위를 나타내는 숫자이며, 두 번째 원소는 실제 데이터이다. 숫자가 작을수록 우선순위가 높다.
import queue
q = queue.Queue()import queue
q = queue.LifoQueue()import queue
q = queue.PriorityQueue()각 큐 클래스는 put(), get(), empty(), full() 등의 메서드를 제공하여 큐를 사용할 수 있도록 한다. 이 메서드들은 각 큐의 특성에 맞게 동작한다.
LifoQueue() 예제
import queue
# LifoQueue 생성
q = queue.LifoQueue()
# 데이터 삽입
q.put("apple")
q.put("banana")
q.put("cherry")
# 데이터 꺼내기
first_item = q.get()
print(first_item) # "cherry" 출력
second_item = q.get()
print(second_item) # "banana" 출력위 예제에서, LifoQueue()는 스택과 같이 작동하기 때문에, 가장 마지막에 삽입된 "cherry"가 가장 먼저 꺼내진다.
PriorityQueue() 예제
import queue
# PriorityQueue 생성
q = queue.PriorityQueue()
# 데이터 삽입 (우선순위, 데이터) 형식으로 삽입
q.put((3, "apple"))
q.put((2, "banana"))
q.put((1, "cherry"))
# 데이터 꺼내기
first_item = q.get()
print(first_item) # (1, "cherry") 출력
second_item = q.get()
print(second_item) # (2, "banana") 출력위 예제에서, PriorityQueue()는 우선순위에 따라 데이터를 꺼낸다. 여기서 우선순위는 첫 번째 요소로 표시되며, 숫자가 작을수록 우선순위가 높다. 따라서 "cherry"가 가장 먼저, 그 다음으로 "banana"가 꺼내진다.
queue 메서드
파이썬의 queue 모듈은 큐 자료구조를 사용하기 위한 다음과 같은 메서드를 제공한다.
- queue.Queue(maxsize): maxsize 인자를 이용해 큐의 최대 크기를 설정할 수 있다. maxsize가 0 이하이면, 큐의 크기는 무한대다.
- q.put(item): item을 큐의 뒤쪽에 추가한다. 만약 큐가 가득 차 있으면(즉, maxsize가 0이 아니며 현재 항목 수가 maxsize와 같다면), 공간이 생길 때까지 블록된다.
- q.get(): 큐의 앞쪽에서 항목을 제거하고 그 항목을 반환한다. 만약 큐가 비어 있으면, 항목이 들어올 때까지 블록된다.
- q.full(): 큐가 가득 차 있으면 True를 반환하고, 그렇지 않으면 False를 반환한다.
- q.empty(): 큐가 비어 있으면 True를 반환하고, 그렇지 않으면 False를 반환한다.
- q.qsize(): 큐에 현재 있는 항목 수를 반환한다.
- q.put_nowait(item): put(item)과 동일하지만, 큐가 가득 차 있으면 queue.Full 예외를 발생시킨다.
- q.get_nowait(): get()과 동일하지만, 큐가 비어 있으면 queue.Empty 예외를 발생시킨다.
- q.join(): 큐에 있는 모든 항목이 처리될 때까지 블록된다. 큐에 있는 각 항목에 대해 get()을 호출한 후에 task_done()을 호출해야 한다.
- q.task_done(): 큐에 있는 항목의 처리가 끝났음을 알린다. 각 get()에 대해 한 번씩 호출해야 합니다. 이 메서드를 호출하면, join() 메서드에 의해 블록되는 것을 해제할 수 있다.
LifoQueue와 PriorityQueue는 Queue와 동일한 메서드를 제공하나, 데이터를 꺼내는 순서가 다르다.
리스트 변수로 큐를 다루는 enqueue, dequeue기능 구현해보기
queue_list = list()
def enqueue(data):
queue_list.append(data)
def dequeue():
data = queue_list[0]
del queue_list[0]
return data