Navbatlar
Navbat - bu birinchi kelgan birinchi chiqish (FIFO) tamoyiliga amal qiluvchi chiziqli ma’lumotlar strukturasi.
Navbatlar
Navbatni supermarketda navbatda turgan odamlar deb tasavvur qiling.
Navbatga birinchi bo‘lib kelgan odam ham birinchi bo‘lib pul to‘lay oladi va supermarketni tark etadi.
Navbatda bajarishimiz mumkin bo‘lgan asosiy operatsiyalar:
- Navbat: Navbatga yangi element qo‘shadi.
- Dequeue: Navbatdan birinchi (old) elementni olib tashlaydi va qaytaradi.
- Peek: Navbatdagi birinchi elementni qaytaradi.
- isEmpty: navbat bo‘sh yoki yo‘qligini tekshiradi.
- Hajmi: Navbatdagi elementlar sonini topadi.
Navbatlar massivlar yoki bog‘langan listlar yordamida amalga oshirilishi mumkin.
Navbatlar ofis printeri uchun ishni rejalashtirishni amalga oshirish, elektron chiptalar uchun tartiblarni qayta ishlash yoki grafiklarda birinchi bo‘lib qidirish algoritmlarini yaratish uchun ishlatilishi mumkin.
Navbatlar ko‘pincha Stacks bilan birga eslatib o‘tiladi, bu avvalgi sahifada tasvirlangan o‘xshash ma’lumotlar tuzilmasi.
Python ro‘yxatlari yordamida navbatni amalga oshirish
Python ro‘yxatlari (va massivlar) uchun Queue quyidagicha ko‘rinishi va o‘zini tutishi mumkin:
Add: Remove:Python ro‘yxatlari navbatlarni amalga oshirish uchun zarur bo‘lgan funksionallikni yaxshi qo‘llab-quvvatlaganligi sababli, biz navbat yaratishdan boshlaymiz va bir nechta qatorlar bilan navbat operatsiyalarini bajaramiz:
Misol
Python ro‘yxatidan navbat sifatida foydalanish:
queue = []
# Enqueue
queue.append('A')
queue.append('B')
queue.append('C')
print("Queue: ", queue)
# Peek
frontElement = queue[0]
print("Peek: ", frontElement)
# Dequeue
poppedElement = queue.pop(0)
print("Dequeue: ", poppedElement)
print("Queue after Dequeue: ", queue)
# isEmpty
isEmpty = not bool(queue)
print("isEmpty: ", isEmpty)
# Size
print("Size: ", len(queue))
O‘zingiz sinab ko‘ring »
Eslatma: Ro‘yxatni ishlatish oddiy bo‘lsa-da, elementlarni boshidan olib tashlash (navbatdan chiqarish operatsiyasi) qolgan barcha elementlarni siljitishni talab qiladi, bu esa katta navbatlar uchun unchalik samarali emas.
Navbat sinfini amalga oshirish
Queue sinfining to‘liq amalga oshirilishi:
Misol
Python sinfidan navbat sifatida foydalanish:
class Queue:
def __init__(self):
self.queue = []
def enqueue(self, element):
self.queue.append(element)
def dequeue(self):
if self.isEmpty():
return "Queue is empty"
return self.queue.pop(0)
def peek(self):
if self.isEmpty():
return "Queue is empty"
return self.queue[0]
def isEmpty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
# Create a queue
myQueue = Queue()
myQueue.enqueue('A')
myQueue.enqueue('B')
myQueue.enqueue('C')
print("Queue: ", myQueue.queue)
print("Peek: ", myQueue.peek())
print("Dequeue: ", myQueue.dequeue())
print("Queue after Dequeue: ", myQueue.queue)
print("isEmpty: ", myQueue.isEmpty())
print("Size: ", myQueue.size())
O‘zingiz sinab ko‘ring »
Bog‘langan listlar yordamida navbatni amalga oshirish
Bog‘langan list qandaydir ma’lumotlarga ega bo‘lgan tugunlardan va keyingi tugunga ko‘rsatgichdan iborat.
Bog‘langan ro‘yxatlardan foydalanishning katta foydasi shundaki, tugunlar xotirada bo‘sh joy bo‘lgan joyda saqlanadi, elementlar massivlarda saqlangan kabi tugunlarni bir-biridan keyin bir-biriga yaqin joyda saqlash shart emas. Bog‘langan listlarning yana bir yaxshi tomoni shundaki, tugunlarni qo‘shish yoki o‘chirishda ro‘yxatdagi qolgan tugunlarni siljitish shart emas.
Navbatlarni amalga oshirish uchun massivlar yoki bog‘langan ro‘yxatlardan foydalanishning afzalliklarini yaxshiroq tushunish uchun massivlar va bog‘langan listlar xotirada qanday saqlanishini tushuntiruvchi ushbu sahifani ko‘rib chiqishingiz kerak.
Bog‘langan list yordamida navbatni shunday amalga oshirish mumkin.
Misol
Bog‘langan ro‘yxat yordamida navbat (Queue) yaratish:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
self.length = 0
def enqueue(self, element):
new_node = Node(element)
if self.rear is None:
self.front = self.rear = new_node
self.length += 1
return
self.rear.next = new_node
self.rear = new_node
self.length += 1
def dequeue(self):
if self.isEmpty():
return "Queue is empty"
temp = self.front
self.front = temp.next
self.length -= 1
if self.front is None:
self.rear = None
return temp.data
def peek(self):
if self.isEmpty():
return "Queue is empty"
return self.front.data
def isEmpty(self):
return self.length == 0
def size(self):
return self.length
def printQueue(self):
temp = self.front
while temp:
print(temp.data, end=" -> ")
temp = temp.next
print()
# Create a queue
myQueue = Queue()
myQueue.enqueue('A')
myQueue.enqueue('B')
myQueue.enqueue('C')
print("Queue: ", end="")
myQueue.printQueue()
print("Peek: ", myQueue.peek())
print("Dequeue: ", myQueue.dequeue())
print("Queue after Dequeue: ", end="")
myQueue.printQueue()
print("isEmpty: ", myQueue.isEmpty())
print("Size: ", myQueue.size())
O‘zingiz sinab ko‘ring »
Navbatlarni amalga oshirish uchun bog‘langan ro‘yxatlardan foydalanish sabablari:
- Dinamik o‘lcham: navbat massivlardan farqli o‘laroq, dinamik ravishda o‘sishi va qisqarishi mumkin.
- O‘zgartirish yo‘q: Navbatning oldingi elementi xotiradagi boshqa elementlarni siljitmasdan olib tashlanishi (dequeue) mumkin.
Navbatlarni amalga oshirish uchun bog‘langan ro‘yxatlardan foydalanmaslik sabablari:
- Qo‘shimcha xotira: Har bir navbat elementi keyingi elementga (keyingi bog‘langan list tuguniga) manzilni o‘z ichiga olishi kerak.
- O‘qilishi: Ba’zilar uchun kodni o‘qish va yozish qiyinroq bo‘lishi mumkin, chunki u uzoqroq va murakkabroq.
Umumiy navbat ilovalari
Navbatlar ko‘plab real stsenariylarda qo‘llaniladi:
- Operatsion tizimlarda vazifalarni rejalashtirish
- Grafiklarda kenglik-birinchi qidiruv
- Tarqalgan tizimlarda xabarlar navbatlari
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!