Черга

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