DSA navbatlar

Navbatlar

Navbat — ko‘plab elementlarni saqlay oladigan ma’lumotlar tuzilmasi.

{{ x.dieNmbr }}

{{ resultText }}: {{ currVal }}

enqueue() dequeue() peek() isEmpty() size()

Navbatni supermarketda navbatda turgan odamlar deb tasavvur qiling.

Navbatga birinchi turgan odam birinchi bo‘lib to‘lov qilib, supermarketdan chiqib keta oladi. Elementlarni bunday tartibda tashkil etish FIFO deb ataladi: First In First Out (birinchi kirgan birinchi chiqadi).

Navbat ustida bajarishimiz mumkin bo‘lgan asosiy amallar:

• Enqueue: Navbatga yangi element qo‘shadi.
• Dequeue: Navbatdagi birinchi (eng oldingi) elementni olib tashlaydi va qaytaradi.
• Peek: Navbatdagi birinchi elementni qaytaradi.
• isEmpty: Navbat bo‘sh yoki bo‘sh emasligini tekshiradi.
• Size: Navbatdagi elementlar sonini aniqlaydi.

Yuqoridagi navbat animatsiyasida ushbu asosiy amallarni sinab ko‘ring.

Navbatlarni massivlar yoki bog‘langan ro‘yxatlar yordamida amalga oshirish mumkin.

Navbatlardan ofis printeri uchun vazifalarni rejalashtirishda, elektron chiptalar bo‘yicha buyurtmalarni qayta ishlashda yoki graflarda kenglik bo‘yicha qidiruv algoritmlarini yaratishda foydalanish mumkin.

Navbatlar ko‘pincha steklar bilan birga tilga olinadi. Stek — oldingi sahifada tasvirlangan o‘xshash ma’lumotlar tuzilmasi.

Navbatni massivlar yordamida amalga oshirish

Navbatlarni amalga oshirishda massivlar yoki bog‘langan ro‘yxatlardan foydalanishning afzalliklarini yaxshiroq tushunish uchun massivlar va bog‘langan ro‘yxatlar xotirada qanday saqlanishini tushuntiruvchi ushbu sahifani ko‘rib chiqing.

Massivdan navbat sifatida foydalanganimizda u quyidagicha ko‘rinadi:

Navbatlarni massivlar yordamida amalga oshirish sabablari:

• Xotirani tejaydi: Massiv elementlari bog‘langan ro‘yxat tugunlari kabi keyingi elementning manzilini saqlamaydi.
• Amalga oshirish va tushunish osonroq: Navbatlarni massivlar yordamida amalga oshirish bog‘langan ro‘yxatlardan foydalanishga qaraganda kamroq kod talab qiladi va shu sababli odatda tushunish ham osonroq.

Navbatlarni amalga oshirishda massivlardan foydalanmaslik sabablari:

• Qat’iy o‘lcham: Massiv xotiraning belgilangan qismini egallaydi. Bu shuni anglatadiki, u keragidan ko‘proq xotira egallashi mumkin yoki massiv to‘lib qolsa, unga boshqa element sig‘maydi. Massiv o‘lchamini o‘zgartirish esa qimmatga tushishi mumkin.
• Siljitish xarajati: Dequeue navbatdagi birinchi elementni olib tashlaydi va qolgan elementlar olib tashlangan element o‘rnini egallash uchun siljitilishi kerak. Bu samarasiz va, ayniqsa, navbat uzun bo‘lsa, muammolarga olib kelishi mumkin.
• Muqobillar: Ba’zi dasturlash tillarida navbat amallari uchun optimallashtirilgan, massivlardan foydalanishdan ko‘ra yaxshiroq bo‘lgan o‘rnatilgan ma’lumotlar tuzilmalari mavjud.

Python ro‘yxatlari navbatlarni amalga oshirish uchun kerakli funksionallikni yaxshi qo‘llab-quvvatlagani sababli, navbat yaratish va navbat amallarini bajarishni atigi bir necha qator kod bilan boshlaymiz:

queue = []

# Enqueue
queue.append('A')
queue.append('B')
queue.append('C')
print("Queue: ", queue)

# Dequeue
element = queue.pop(0)
print("Dequeue: ", element)

# Peek
frontElement = queue[0]
print("Peek: ", frontElement)

# isEmpty
isEmpty = not bool(queue)
print("isEmpty: ", isEmpty)

# Size
print("Size: ", len(queue))

Biroq navbatlar uchun asosiy amallarga ega ma’lumotlar tuzilmasini aniq yaratish uchun buning o‘rniga navbat sinfini (class) yaratishimiz kerak. Python’da navbatlarni bu tarzda yaratish C va Java kabi boshqa dasturlash tillarida navbatlar yaratilishiga ham ko‘proq o‘xshaydi.

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("Dequeue: ", myQueue.dequeue())

print("Peek: ", myQueue.peek())

print("isEmpty: ", myQueue.isEmpty())

print("Size: ", myQueue.size())

Navbatni bog‘langan ro‘yxatlar yordamida amalga oshirish

Navbatlarni bog‘langan ro‘yxatlar yordamida amalga oshirish sabablari:

• Dinamik o‘lcham: Massivlardan farqli ravishda, navbat dinamik ravishda kattalashishi va kichrayishi mumkin.
• Siljitishsiz: Navbatning oldingi elementini xotiradagi boshqa elementlarni siljitmasdan olib tashlash (dequeue) mumkin.

Navbatlarni amalga oshirishda bog‘langan ro‘yxatlardan foydalanmaslik sabablari:

• Qo‘shimcha xotira: Har bir navbat elementi keyingi elementning (bog‘langan ro‘yxatdagi keyingi tugunning) manzilini saqlashi kerak.
• O‘qilishi: Kod uzunroq va murakkabroq bo‘lgani uchun ba’zilarga uni o‘qish va yozish qiyinroq bo‘lishi mumkin.

Navbatni bog‘langan ro‘yxat yordamida quyidagicha amalga oshirish mumkin.

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("Dequeue: ", myQueue.dequeue())

print("Peek: ", myQueue.peek())

print("isEmpty: ", myQueue.isEmpty())

print("Size: ", myQueue.size())

enqueue(7): 
    value 7 is placed on 
    index  in the array.

dequeue(): 
    value  is taken 
    out of the queue.