Очередь

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

2

Задача

Модуль 1: Python Core, 15 уровень, 6 лекция

Недоступна

Очередь это просто

Очередь это просто

Открыть

2

Задача

Модуль 1: Python Core, 15 уровень, 6 лекция

Недоступна

Очередь это сложно

Очередь это сложно

Открыть