</> Softromeda Edu

6-bo‘lim

Navbat (Queue)

FIFO prinsipi, navbatni to'g'ri amalga oshirish, deque, aylanma navbat va prioritetli navbat bilan tanishuv.

🕑 9 daqiqa o‘qish 📄 586 so‘z 👁 7 marta ko‘rilgan
Ushbu bo‘lim mundarijasi
  1. FIFO prinsipi
  2. Sodda, lekin noto'g'ri yechim
  3. To'g'ri yechim: deque
  4. deque ning boshqa imkoniyatlari
  5. Aylanma navbat (Circular Queue)
  6. Prioritetli navbat
  7. Stek va navbat taqqoslanishi
  8. Navbat qayerda ishlatiladi?
  9. Xulosa

Stek "oxirgi kirgan birinchi chiqadi" bo'lsa, navbat hayotdagi oddiy navbat kabi ishlaydi: birinchi kelgan birinchi xizmat oladi.

FIFO prinsipi #

FIFO - First In, First Out.

dequeue() chiqish A B C D bosh oxir enqueue(E) kirish Bir tomondan kiradi, boshqa tomondan chiqadi
Navbatda elementlar bir uchidan kirib, ikkinchi uchidan chiqadi
AmalVazifasiMurakkablik
enqueue(x)Oxiriga qo'shadiO(1)
dequeue()Boshidan oladiO(1)
peek()Boshdagini ko'radiO(1)
bosh_mi()Bo'shligini tekshiradiO(1)

Sodda, lekin noto'g'ri yechim #

Python
navbat = []
navbat.append("A")        # enqueue - O(1), yaxshi
birinchi = navbat.pop(0)  # dequeue - O(n), YOMON!
list.pop(0) navbatni buzadi

pop(0) qolgan barcha elementni bir pozitsiyaga suradi. 100 000 ta elementli navbatda har bir dequeue 100 000 ta ko'chirish demakdir. Natijada O(1) bo'lishi kerak bo'lgan amal O(n) bo'lib qoladi.

Farqni o'lchab ko'ramiz:

Python
import time
from collections import deque

N = 100_000

royxat = list(range(N))
boshlanish = time.perf_counter()
while royxat:
    royxat.pop(0)
print(f"list.pop(0):     {time.perf_counter() - boshlanish:.4f} soniya")

navbat = deque(range(N))
boshlanish = time.perf_counter()
while navbat:
    navbat.popleft()
print(f"deque.popleft(): {time.perf_counter() - boshlanish:.4f} soniya")
Natija
list.pop(0):     1.8642 soniya
deque.popleft(): 0.0071 soniya

260 barobar farq.

To'g'ri yechim: deque #

collections.deque ikki tomonlama bog'langan ro'yxat asosida qurilgan va ikkala uchida ham O(1) ishlaydi.

Python
from collections import deque


class Navbat:
    """FIFO navbat - barcha amallar O(1)."""

    def __init__(self):
        self._elementlar = deque()

    def enqueue(self, qiymat):
        """Oxiriga qo'shadi. O(1)."""
        self._elementlar.append(qiymat)

    def dequeue(self):
        """Boshidan oladi. O(1)."""
        if self.bosh_mi():
            raise IndexError("Navbat bo'sh")
        return self._elementlar.popleft()

    def peek(self):
        if self.bosh_mi():
            raise IndexError("Navbat bo'sh")
        return self._elementlar[0]

    def bosh_mi(self):
        return len(self._elementlar) == 0

    def __len__(self):
        return len(self._elementlar)

    def __str__(self):
        return "bosh -> " + " -> ".join(str(q) for q in self._elementlar) + " -> oxir"


navbat = Navbat()
for mijoz in ["Husanboy", "Sardor", "Malika"]:
    navbat.enqueue(mijoz)

print(navbat)
print("Xizmat ko'rsatildi:", navbat.dequeue())
print("Navbatdagi keyingi:", navbat.peek())
print(navbat)
Natija
bosh -> Husanboy -> Sardor -> Malika -> oxir
Xizmat ko'rsatildi: Husanboy
Navbatdagi keyingi: Sardor
bosh -> Sardor -> Malika -> oxir

deque ning boshqa imkoniyatlari #

Python
from collections import deque

d = deque([1, 2, 3])

d.append(4)          # o'ngga qo'shish      O(1)
d.appendleft(0)      # chapga qo'shish      O(1)
print(d)

print(d.pop())       # o'ngdan olish        O(1)
print(d.popleft())   # chapdan olish        O(1)

d.rotate(1)          # aylantirish
print(d)

# Oxirgi N ta elementni saqlash uchun ideal
oxirgi_uchta = deque(maxlen=3)
for son in range(1, 8):
    oxirgi_uchta.append(son)
print(oxirgi_uchta)
Natija
deque([0, 1, 2, 3, 4])
4
0
deque([3, 1, 2])
deque([5, 6, 7], maxlen=3)
maxlen juda foydali

deque(maxlen=n) to'lganda eng eski elementni avtomatik chiqarib tashlaydi. Bu jurnalning oxirgi 100 satri, o'yin tarixidagi oxirgi 10 harakat yoki harorat sensorining oxirgi o'lchovlarini saqlash uchun ideal.

Aylanma navbat (Circular Queue) #

Cheklangan hajmli massivda navbat qurishning eng samarali usuli. Massiv oxiriga yetganda indeks boshiga qaytadi.

A [0] B [1] C [2] bo'sh [3] bo'sh [4] bo'sh [5] Ikkita ko'rsatkich: bosh → qayerdan olinadi (indeks 0) oxir → qayerga qo'yiladi (indeks 3) keyingi = (joriy + 1) % hajm qoldiq amali indeksni boshiga qaytaradi
Massiv oxiriga yetganda indeks % amali orqali boshiga qaytadi
Python
class AylanmaNavbat:
    """Belgilangan hajmli aylanma navbat. Barcha amallar O(1)."""

    def __init__(self, hajm):
        self._hajm = hajm
        self._elementlar = [None] * hajm
        self._bosh = 0
        self._soni = 0

    def enqueue(self, qiymat):
        if self.toliq_mi():
            raise OverflowError("Navbat to'lgan")
        oxir = (self._bosh + self._soni) % self._hajm
        self._elementlar[oxir] = qiymat
        self._soni += 1

    def dequeue(self):
        if self.bosh_mi():
            raise IndexError("Navbat bo'sh")
        qiymat = self._elementlar[self._bosh]
        self._elementlar[self._bosh] = None
        self._bosh = (self._bosh + 1) % self._hajm
        self._soni -= 1
        return qiymat

    def bosh_mi(self):
        return self._soni == 0

    def toliq_mi(self):
        return self._soni == self._hajm

    def __str__(self):
        return f"{self._elementlar}  (bosh={self._bosh}, soni={self._soni})"


navbat = AylanmaNavbat(4)
for harf in "ABC":
    navbat.enqueue(harf)
print(navbat)

navbat.dequeue()
navbat.dequeue()
print(navbat)

navbat.enqueue("D")
navbat.enqueue("E")      # boshiga aylanib o'tadi
print(navbat)
Natija
['A', 'B', 'C', None]  (bosh=0, soni=3)
[None, None, 'C', None]  (bosh=2, soni=1)
[None, None, 'C', 'D']  (bosh=2, soni=3)

Oxirgi holatda E indeks 0 ga tushdi - navbat aylanib boshiga qaytdi.

Qayerda ishlatiladi?

Aylanma navbat - klaviatura buferi, audio va video oqim buferi, tarmoq paketlari navbati va operatsion tizim rejalashtiruvchisining asosi. Xotira oldindan ajratilgani uchun u real vaqt tizimlarida ayniqsa qadrlanadi.

Prioritetli navbat #

Ba'zan navbat tartibi kelish vaqtiga emas, muhimlikka bog'liq bo'ladi. Kasalxona qabulxonasida og'ir bemor navbatsiz kiradi.

Python
import heapq


class PrioritetliNavbat:
    """Kichik raqam = yuqori prioritet."""

    def __init__(self):
        self._uyum = []
        self._hisoblagich = 0        # bir xil prioritetda tartibni saqlaydi

    def qosh(self, element, prioritet):
        """O(log n)."""
        heapq.heappush(self._uyum, (prioritet, self._hisoblagich, element))
        self._hisoblagich += 1

    def ol(self):
        """Eng yuqori prioritetlisini qaytaradi. O(log n)."""
        if not self._uyum:
            raise IndexError("Navbat bo'sh")
        return heapq.heappop(self._uyum)[2]

    def __len__(self):
        return len(self._uyum)


qabulxona = PrioritetliNavbat()
qabulxona.qosh("Husanboy - shamollash", 3)
qabulxona.qosh("Sardor - suyak sinishi", 1)
qabulxona.qosh("Malika - bosh og'rig'i", 3)
qabulxona.qosh("Bekzod - yurak xurujii", 0)

print("Qabul tartibi:")
while len(qabulxona):
    print("  -", qabulxona.ol())
Natija
Qabul tartibi:
  - Bekzod - yurak xurujii
  - Sardor - suyak sinishi
  - Husanboy - shamollash
  - Malika - bosh og'rig'i

Diqqat qiling: bir xil prioritetli Husanboy va Malika kelish tartibida qoldi - buni _hisoblagich ta'minladi.

Prioritetli navbat uyumga tayanadi

Ichkarida heapq uyum (heap) tuzilmasini ishlatadi. Uni 10-bo'limda batafsil ko'ramiz. Hozircha bilish yetarli: qo'shish va olish O(log n), eng muhimini ko'rish esa O(1).

Stek va navbat taqqoslanishi #

StekNavbat
PrinsipLIFOFIFO
Qo'shishYuqorigaOxiriga
OlishYuqoridanBoshidan
Python vositasilistdeque
AlgoritmDFSBFS
Hayotiy misolLikopchalar uyumiDo'kondagi navbat
SohaQo'llanilishi
Operatsion tizimJarayonlarni rejalashtirish
PrinterChop etish navbati
Veb-serverlarKelayotgan so'rovlar navbati
Xabar brokerlariRabbitMQ, Kafka
AlgoritmlarBFS - kenglik bo'yicha qidiruv
O'yinlarHodisalar navbati
Amaliy topshiriq
  1. Navbat klassidan foydalanib bankdagi navbat simulyatorini yozing: mijozlar keladi, har biriga xizmat 3 daqiqa, kutish vaqtini hisoblang.
  2. Ikkita stek yordamida navbat yasang (klassik intervyu savoli).
  3. deque bilan matn palindrom ekanini tekshiring - ikkala uchdan bir vaqtda solishtiring.
  4. Prioritetli navbat yordamida vazifalar boshqaruvchisini yozing: muhimlik darajasi bo'yicha saralansin.

Xulosa #

  • Navbat FIFO prinsipida ishlaydi: birinchi kirgan birinchi chiqadi.
  • Python'da navbat uchun collections.deque ishlating, list.pop(0) emas.
  • deque ikkala uchida ham O(1), maxlen bilan avtomatik cheklanadi.
  • Aylanma navbat cheklangan massivda % amali orqali samarali ishlaydi.
  • Prioritetli navbat tartibni kelish vaqtiga emas, muhimlikka qarab belgilaydi.

Keyingi bo'limda eng tez qidiruvni ta'minlaydigan tuzilma - xesh-jadval bilan tanishamiz.

Xatolik topdingizmi?

Imlo xatosi, ishlamaydigan kod yoki noto‘g‘ri ma‘lumotni ko‘rsangiz - bizga xabar bering. Har bir xabar administrator tomonidan ko‘rib chiqiladi.