10-Маъруза: Steklar va navbatlar. Ularni mantiqiy tasvirlash va utida amallar bajarish algoritmi. Reja

Navbat va uning tadbiqi

Navbat – bu elementlarning tartiblangan to’plami bo’lib, bunda elementlarni qo’shish bir tomondan – tuzilma oxiridan (bu navbat oxiri deb ataladi), elementlarni o’chirish esa, tuzilmaning ikkinchi oxiri – navbat boshi deb ataluvchi tomonidan ruxsat beriladi.

NAVBATGA HAYOTDAN MISOLLAR.
Navbatning barchamizga tanish bo’lgan modeli – bu do’kondagi xaridorlar tomonidan hosil qilingan navbat hisoblanadi. Navbat FIFO (First In - First Out) – birinchi kelgan birinchi ketadi turidagi tuzilma sifatida qaraladi. Rasmda 3 ta elementdan tashkil topgan navbat tuzilmasiga misol keltirilgan.
2-rasm. Navbatning mantiqiy ko’rinishi
Navbat tuzilmasi ommaviy xizmat ko’rsatish masalalarini modellashtirishda ham qo’llaniladi (masalan, banklarda mijozlarga xizmat ko’rsatish).


Navbatni massiv yordamida tadbiq qilish. Agarda navbatning maksimal o’lchami oldindan ma’lum bo’lsa, dasturda uni massiv ko’rinishida tadbiq qilish mumkin. Bitta tuzilmada massivning o’zini va uning o’lchamini birlashtirish juda qulay. 100 ta (butun sonli) elementdan iborat yangi ma’lumot turini – navbatni e’lon qilamiz.
Stek bir tomondan “yopiq” (harakatlanmaydigan) bo’lsa, navbat ikki tomonlama “harakatlanuvchi” hisoblanadi. Shuning uchun ham navbatda ikkita o’zgaruvchi qo’llaniladi, bular navbat boshi head va navbat oxiri tail. Bu o’zgaruvchilarning birinchisi navbatning birinchi elementini, ikkinchisi esa navbatning oxirgi elementining tartib raqamini bildiradi. Agar bu o’zgaruvchilar teng bo’lsa, navbatda bor-yo’g’i bitta element mavjud bo’ladi. Massiv halqasimon shaklda biriktiriladi, lekin bunda massiv boshida bo’sh joylar mavjud bo’ladi. Yangi element rasmda ko’rsatilganidek navbat boshidan qo’shiladi.
3-rasm. Navbatga element qo’shish sxemasi
Navbat bilan ishlash uchun ikkida amalning, ya’ni navbat oxiridan element qo’shish (PushTail) va navbat boshidan elementni o’chirish (Pop) amallarining qanday bajarilishini aniqlab olish kerak bo’ladi
Navbat har doim ham massiv boshidan boshlanmasligi mumkin (ba’zi elementlar oldindan tanlab “olingan”ligi hisobidan), Q.tail bir birlikka oshirgandan keyin massiv chegarasidan chiqib ketmaslikni tekshirib ko’rish zarur bo’ladi. Agarda chegaradan chiqish holati ro’y bersa, yangi element massiv boshiga yoziladi. Yuqoridagi protsedurada “navbat to’la” xatoligi qayta ishlangan. Bunday holda ekranga “Navbat to’la” xabari chiqariladi. Xuddi shunday PushTail, funktsiyasini ham yozish mumkin. Bu funktsiya element qo’shilganda 1, xatolik yuz berganda esa 0 qiymatni qaytaradi.
Shunga alohida diqqat qilish zarurki, Q navbat protsedurada ko’rsatkich orqali berilgan, aslida bu tuzilmaning xotira adresini aniqlaydi.