Kolejka

7.1 Definicja kolejki i jej właściwości

Kolejka — to abstrakcyjna struktura danych, która jest uporządkowaną kolekcją elementów zorganizowaną na zasadzie "pierwsze przyszło — pierwsze wyszło" (First In, First Out, FIFO). Kolejkę można sobie wyobrazić jako linię ludzi w sklepie: pierwszy w kolejce jest obsługiwany jako pierwszy.

Właściwości kolejki:

• FIFO (First In, First Out): Pierwszy dodany element będzie pierwszym usuniętym elementem.
• Ograniczone operacje: Kolejka obsługuje ograniczony zestaw operacji — dodawanie (enqueue), usuwanie (dequeue) i podgląd (peek) elementu na przedniej pozycji.
• Jednokierunkowy dostęp: Dostęp do elementów jest możliwy tylko z przedniej (front) i tylnej (rear) strony.
• Prostota implementacji: Kolejkę można łatwo zaimplementować za pomocą tablicy lub listy powiązanej.

Zasada działania FIFO:

• Dodawanie elementu (enqueue): Nowy element jest dodawany na koniec kolejki.
• Usuwanie elementu (dequeue): Pierwszy dodany element jest usuwany z początku kolejki.
• Podgląd przedniego elementu (peek): Pozwala zobaczyć element na przedniej pozycji kolejki bez jego usuwania.

Elementy kolejki dodawane są z jednego końca (tylnej części) i usuwane z innego końca (przedniej części). W ten sposób pierwszy dodany element okazuje się pierwszym usuniętym.

7.2 Podstawowe operacje

Podstawowe operacje: enqueue, dequeue, peek

Operacja enqueue: Dodaje nowy element na koniec kolejki.

Złożoność czasowa: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Wyjście: deque([10, 20])

Operacja dequeue: Usuwa i zwraca element z początku kolejki.

Złożoność czasowa: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Wyjście: deque([10, 20])

front_element = queue.popleft()  # dequeue
print(front_element)  # Wyjście: 10
print(queue)  # Wyjście: deque([20])

Operacja peek: Zwraca element na przedniej pozycji kolejki bez jego usuwania.

Złożoność czasowa: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Wyjście: deque([10, 20])

front_element = queue[0]  # peek
print(front_element)  # Wyjście: 10

7.3 Przykłady użycia kolejki

Rozważmy kilka przykładów użycia kolejki.

1 Zarządzanie zadaniami na drukarce

Kolejka jest używana do zarządzania zadaniami na drukarce, gdzie dokumenty dodawane są do kolejki i drukowane w kolejności ich przybycia.

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"Drukowanie: {job}")

# Przykład użycia:
printer_queue = PrinterQueue()
printer_queue.add_job("Document1.pdf")
printer_queue.add_job("Document2.pdf")
printer_queue.print_job()  # Wyjście: Drukowanie: Document1.pdf
printer_queue.print_job()  # Wyjście: Drukowanie: Document2.pdf

2 Przetwarzanie żądań na serwerze WWW

Kolejka jest używana do zarządzania żądaniami klientów trafiającymi na serwer WWW. Żądania są przetwarzane w kolejności ich przybycia.

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"Przetwarzanie żądania: {request}")

# Przykład użycia:
request_queue = RequestQueue()
request_queue.add_request("GET /index.html")
request_queue.add_request("POST /submit-form")
request_queue.process_request()  # Wyjście: Przetwarzanie żądania: GET /index.html
request_queue.process_request()  # Wyjście: Przetwarzanie żądania: POST /submit-form

3 Kolejka wiadomości w systemach wymiany wiadomości

Kolejka jest używana do zarządzania wiadomościami w systemach wymiany informacji (np. w brokerach wiadomości). Wiadomości są przetwarzane w kolejności ich przybycia.

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"Otrzymano wiadomość: {message}")

# Przykład użycia:
message_queue = MessageQueue()
message_queue.send_message("Hello")
message_queue.send_message("World")
message_queue.receive_message()  # Wyjście: Otrzymano wiadomość: Hello
message_queue.receive_message()  # Wyjście: Otrzymano wiadomość: World