|
Ma’lumotlar tuzilmasi va algoritmlar” fanidan 2-mustaqil ishi tuzuvchi: Qo’ziboyev Xasanboy
|
| bet | 3/4 | | Sana | 16.12.2023 | | Hajmi | 356,54 Kb. | | #120363 |
Bog'liq Xasanboy MT MaruzaNatija:
3-MASALA
3-masala. Navbat tuzilmasini bog‘langan ro‘yxat orqali qayta ishlashga misol:
Muammoni hal qilish uchun quyidagilarga amal qiling:
- tuzilma uchun ikkita ko'rsatgich: front va back tanlab olish, bu ko‘rsatkichlar mos ravishda navbatning birinchi va oxirgi elementiga ishora qiladi.
- enQueue() – navbat oxiridan element qo'shadi va backni keyingi elementga o'tkazadi.
- deQueue() – navbat boshidan elementni olib tashlaydi va frontni keyingi elementga o'tkazadi.
Masalan:
Masalaning qo‘yilishi:
Bog‘langan ro'yxat yordamida navbatni hosil qiling. Hosil bo‘lgan navbatga element qo‘shish enQueue(x) va elementni o‘chirish deQueue() funksiyalarini yozing.
Bunda navbatga element qo’shish enQueue(x) funktsiyasi uchun 1 x so’rovi – navbatga ‘x’ va elementni o’chirish deQueue() uchun 2 so’rovini ishlab chiqing.
Vaqt murakkabligi: O(1) - enqueue() va dequeue() uchun.
Qo’shimcha xotira murakkabligi: O(1) - enqueue() va dequeue() uchun.
Cheklovlar:
1 ≤ Q ≤ 100
1 ≤ x ≤ 100
Masalaning javobi:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.front = self.back = None
def isEmpty(self):
return self.front is None
def EnQueue(self, item):
#mening kodim
qoshish_elem = Node(item)
if self.back is None:
self.front = self.back = qoshish_elem
print(f"{item} navbatga qo'shildi.")
return
self.back.next = qoshish_elem
self.back = qoshish_elem
print(f"{item} navbatga qo'shildi.")
def DeQueue(self):
#mening kodim
if self.isEmpty():
print("Navbat bo'sh. Element o'chirilmadi.")
return None
ochish_elem = self.front.data
self.front = self.front.next
if self.front is None:
self.back = None
print(f"{ochish_elem} navbatdan o'chirildi.")
return ochish_elem
# Umumiy dastur
if __name__ == "__main__":
my_queue = Queue()
my_queue.EnQueue(10)
my_queue.EnQueue(20)
my_queue.EnQueue(30)
dequeued_item = my_queue.DeQueue()
print(f"O'chirilgan element: {dequeued_item}")
my_queue.EnQueue(40)
my_queue.EnQueue(50)
is_empty = my_queue.isEmpty()
print(f"Navbat bo'shmi? {is_empty}")
|
| |
