큐

7.1 큐의 정의와 속성

큐는 "선입선출" (First In, First Out, FIFO) 원칙에 따라 정리된 요소들의 순차적인 컬렉션을 나타내는 추상 데이터 구조야. 큐는 마치 가게에서 줄 서 있는 사람들처럼: 줄의 첫 번째 사람이 먼저 서비스를 받게 돼.

큐의 속성:

• FIFO (First In, First Out): 처음 추가된 요소가 처음 삭제되는 요소가 돼.
• 제한된 연산: 큐는 제한된 연산 집합을 지원해 — 요소 추가 (enqueue), 제거 (dequeue) 그리고 앞부분 요소 보기 (peek).
• 단방향 접근: 요소는 앞쪽 (front)과 뒤쪽 (rear) 사이드에서만 접근 가능해.
• 간단한 구현: 큐는 배열이나 연결 리스트로 쉽게 구현할 수 있어.

FIFO 작동 원칙:

• 요소 추가 (enqueue): 새로운 요소는 큐의 끝에 추가돼.
• 요소 제거 (dequeue): 처음 추가된 요소가 큐의 시작에서 제거돼.
• 앞부분 요소 보기 (peek): 큐의 앞부분 요소를 제거 없이 볼 수 있게 해.

큐의 요소는 한쪽 끝(뒷부분)에서 추가되고, 다른 끝(앞부분)에서 제거돼. 이렇게 해서 처음 추가된 요소가 처음으로 제거되는 거지.

7.2 주요 연산

주요 연산: enqueue, dequeue, peek

연산 enqueue: 새로운 요소를 큐의 끝에 추가해.

시간 복잡도: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # 출력: deque([10, 20])

연산 dequeue: 큐의 시작에서 요소를 제거하고 반환해.

시간 복잡도: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # 출력: deque([10, 20])

front_element = queue.popleft()  # dequeue
print(front_element)  # 출력: 10
print(queue)  # 출력: deque([20])

연산 peek: 요소를 제거하지 않고 큐의 앞부분 요소를 반환해.

시간 복잡도: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # 출력: deque([10, 20])

front_element = queue[0]  # peek
print(front_element)  # 출력: 10

7.3 큐의 사용 예제

큐 사용의 몇 가지 예제를 살펴보자.

1 프린터 작업 관리

큐는 프린터 작업을 관리하는 데 사용되는데, 여기서 문서들은 큐에 추가되고 도착 순서대로 인쇄돼.

class PrinterQueue:
    def __init__(self):
        self.queue = deque()

    def add_job(self, job):
        self.queue.append(job)

    def print_job(self):
        if self.queue:
            job = self.queue.popleft()
            print(f"Printing: {job}")

# 사용 예제:
printer_queue = PrinterQueue()
printer_queue.add_job("Document1.pdf")
printer_queue.add_job("Document2.pdf")
printer_queue.print_job()  # 출력: Printing: Document1.pdf
printer_queue.print_job()  # 출력: Printing: Document2.pdf

2 웹 서버의 요청 처리

큐는 웹 서버에 도착하는 클라이언트 요청을 관리하는 데 사용돼. 요청은 도착한 순서대로 처리돼.

class RequestQueue:
    def __init__(self):
        self.queue = deque()

    def add_request(self, request):
        self.queue.append(request)

    def process_request(self):
        if self.queue:
            request = self.queue.popleft()
            print(f"Processing request: {request}")

# 사용 예제:
request_queue = RequestQueue()
request_queue.add_request("GET /index.html")
request_queue.add_request("POST /submit-form")
request_queue.process_request()  # 출력: Processing request: GET /index.html
request_queue.process_request()  # 출력: Processing request: POST /submit-form

3 메시지 교환 시스템의 메시지 큐

큐는 메시지 교환 시스템(예: 메시지 브로커)에서 메시지를 관리하는 데 사용돼. 메시지는 도착 순서대로 처리돼.

class MessageQueue:
    def __init__(self):
        self.queue = deque()

    def send_message(self, message):
        self.queue.append(message)

    def receive_message(self):
        if self.queue:
            message = self.queue.popleft()
            print(f"Received message: {message}")

# 사용 예제:
message_queue = MessageQueue()
message_queue.send_message("Hello")
message_queue.send_message("World")
message_queue.receive_message()  # 출력: Received message: Hello
message_queue.receive_message()  # 출력: Received message: World