Növbə

7.1 Növbənin tərifi və onun xüsusiyyətləri

Növbə — bu, "ilk gələn — ilk gedir" (First In, First Out, FIFO) prinsipi əsasında təşkil olunmuş elementlərin ardıcıl kolleksiyasını təqdim edən abstrakt məlumat strukturudur. Növbəni mağazada insanların növbəsi kimi təqdim edə bilərik: növbədə birinci olan şəxs birinci xidmət alır.

Növbənin xüsusiyyətləri:

• FIFO (First In, First Out): Əlavə edilmiş birinci element birinci silinən element olur.
• Məhdud əməliyyatlar: Növbə yalnız məhdud əməliyyatları dəstəkləyir — əlavə etmə (enqueue), silmə (dequeue) və ilk elementə baxma (peek).
• Birtərəfli giriş: Elementlərə yalnız qabaq (front) və arxa (rear) tərəflərdən giriş mümkündür.
• Sadə reallaşdırma: Növbəni asanlıqla array və ya bağlı siyahı ilə reallaşdırmaq olar.

FIFO prinsipi:

• Elementin əlavə edilməsi (enqueue): Yeni element növbənin sonuna əlavə edilir.
• Elementin silinməsi (dequeue): Əlavə edilmiş birinci element növbənin əvvəlindən silinir.
• Qabaq elementə baxma (peek): Qabaq mövqedə olan elementi silmədən görmək imkanı verir.

Növbənin elementləri bir tərəfdən (arxa hissədən) əlavə edilir və digər tərəfdən (qabaq hissədən) silinir. Beləliklə, birinci əlavə edilmiş element birinci silinmiş olur.

7.2 Əsas əməliyyatlar

Əsas əməliyyatlar: enqueue, dequeue, peek

Əməliyyat enqueue: Yeni elementi növbənin sonuna əlavə edir.

Zaman mürəkkəbliyi: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Çıxış: deque([10, 20])

Əməliyyat dequeue: Elementi növbənin əvvəlindən silir və geri qaytarır.

Zaman mürəkkəbliyi: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Çıxış: deque([10, 20])

front_element = queue.popleft()  # dequeue
print(front_element)  # Çıxış: 10
print(queue)  # Çıxış: deque([20])

Əməliyyat peek: Elementi növbənin önündəki mövqedən silmədən geri qaytarır.

Zaman mürəkkəbliyi: O(1).

from collections import deque

queue = deque()
queue.append(10)  # enqueue 10
queue.append(20)  # enqueue 20
print(queue)  # Çıxış: deque([10, 20])

front_element = queue[0]  # peek
print(front_element)  # Çıxış: 10

7.3 Növbənin istifadəsinə misallar

Növbənin istifadəsinə bir neçə nümunəyə baxaq.

1 Printerdə tapşırıqların idarə olunması

Növbə printerdə tapşırıqları idarə etmək üçün istifadə olunur, burada sənədlər növbəyə əlavə olunur və daxilolma sırasına görə çap edilir.

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"Çap olunur: {job}")

# İstifadə nümunəsi:
printer_queue = PrinterQueue()
printer_queue.add_job("Document1.pdf")
printer_queue.add_job("Document2.pdf")
printer_queue.print_job()  # Çıxış: Çap olunur: Document1.pdf
printer_queue.print_job()  # Çıxış: Çap olunur: Document2.pdf

2 Veb-serverdə sorğuların emalı

Növbə müştəri sorğularını idarə etmək üçün istifadə olunur, veb-serverə daxil olan sorğular qəbul olunma sırasına görə emal edilir.

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"Sorğu emal olunur: {request}")

# İstifadə nümunəsi:
request_queue = RequestQueue()
request_queue.add_request("GET /index.html")
request_queue.add_request("POST /submit-form")
request_queue.process_request()  # Çıxış: Sorğu emal olunur: GET /index.html
request_queue.process_request()  # Çıxış: Sorğu emal olunur: POST /submit-form

3 Mesaj növbəsi ilə məlumat mübadiləsi sistemləri

Növbə məlumat mübadiləsi (məsələn, mesaj brokerləri) sistemlərində mesajları idarə etmək üçün istifadə olunur. Mesajlar daxilolma sırasına görə emal edilir.

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"Qəbul edilmiş mesaj: {message}")

# İstifadə nümunəsi:
message_queue = MessageQueue()
message_queue.send_message("Hello")
message_queue.send_message("World")
message_queue.receive_message()  # Çıxış: Qəbul edilmiş mesaj: Hello
message_queue.receive_message()  # Çıxış: Qəbul edilmiş mesaj: World