|
Ma’lumotlar tuzilmasi va algoritmlar” fanidan 2-mustaqil ishi tuzuvchi: Qo’ziboyev Xasanboy
|
| bet | 2/4 | | Sana | 16.12.2023 | | Hajmi | 356,54 Kb. | | #120363 |
Bog'liq Xasanboy MT Maruza2-MASALA
2-masala. Navbatni massiv yordamida tadbiq qilish. Navbat (queue)ni tadbiq qilish uchun navbat boshi (front) va navbat oxiri (back) uchun ikkita indeksni aniqlab olishimiz kerak. Navbatga elementni oxiridan qo’shamiz, elementni navbat boshidan o’chiramiz.
Navbatga element qo’shish algoritmi:
1) Navbatda element bor yoki yo’qligini (to’liqlikka) tekshirish;
2) Agar navbat to’la bo’lsa, to’liq ekanligini chiqarish va ishni yakunlash;
3) Agar to’liq bo’lmasa, back ni bir birlikka oshirib, elementni qo’shish
Navbatdan elementni o’chirish algoritmi:
1) Navbatni bo’sh yoki bo’ emaslikka tekshirish;
2) Agar bo’sh bo’lsa, navbat bo’sh ekanligin chiqarish va ishni yakunlash;
3) Agar bo’sh bo’lmasa, front dan elementni olish va uni bittaga oshirish.
Quyida berilgan navbat klasslari uchun ikkita metodni yozing va dasturdan ishga tushiring. Birinchi metod x elementni navbatga qo’shish, ikkinchi metod navbatdan elementni o’chirish.
Masalan:
Asosiy vazifangiz:
Berilgan namunadagi ikkita funksiyalar enqueue() va dequeue() prototiplari asosida o’zingiz kod yozing. Birinchi funksiya bitta parametr, ya’ni qo’shiladigan elementni qabul qilsin, ikkinchi funksiya esa parametrsiz bo’lib, butun son qaytaradi. Agar navbat bo’sh bo’lsa, -1 qiymatini qaytarsin.
Vaqt murakkabligi: O(1) - enqueue() va dequeue() uchun.
Qo’shimcha xotira murakkabligi: O(1) - enqueue() va dequeue() uchun.
Cheklovlar:
1 ≤ Q ≤ 105
1 ≤ x ≤ 105
Masalaning javobi:
class Queue:
def __init__(self, capacity):
self.front = 0
self.size = 0
self.back = capacity - 1
self.Q = [None] * capacity
self.capacity = capacity
def isFull(self):
return self.size == self.capacity
def isEmpty(self):
return self.size == 0
#meing kodim
def EnQueue(self, item):
if self.isFull():
print("Navbat to'la. Element qo'shilmadi.")
return -1
else:
self.back = (self.back + 1) % self.capacity
self.Q[self.back] = item
self.size += 1
#mening kodim
def DeQueue(self):
if self.isEmpty():
print("Navbat bo'sh. Element o'chirilmadi.")
return -1
else:
ochish_elem = self.Q[self.front]
self.front = (self.front + 1) % self.capacity
self.size -= 1
return ochish_elem
# Umumiy dastur
if __name__ == "__main__":
my_queue = Queue(5)
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}")
|
| |
