“Dasturiy injiniring” fakulteti “MA‟lumotlar tuzilmasi va algoritmlar”

2.2. Navbat 
 
Navbat bu FIFO (First In - First Out - "birinchi kelgan – birinchi ketadi"), 
shunday o„zgaruvchan uzunlikdagi ketma-ketlik, ro„yhatki, unda tuzilmaga 
elementlar faqat bir tomondan, ya‟ni navbatning oxiridan qo„shiladi va 
elementlarni tuzilmadan chiqarish boshqa tomondan, ya‟ni navbat boshidan amalga 
oshiriladi. Navbat ustida bajariladigan asosiy amallar
-
yangi elementni qo„shish,
-
elementni chiqarib tashlash,
-
uzunligini aniqlash,
-
navbatni tozalash.
Navbatni statik xotirada vektor ko„rinishida ifodalashda 2 ta parametr, ya‟ni 
navbat boshini (navbatning 1-elementini) va oxirini (navbatning oxirgi elementini) 
ko„rsatuvchi ko„rsatkichlar olinadi (2.1-rasm).
2.1-rasm. Navbat tuzilmasi 
Navbatga yangi element kiritilayotganda navbat oxiri ko„rsatkichi 
ko„rsatayotgan adresga yoziladi va shundan keyin navbat oxiri ko„rsatkichi bittaga 
oshiriladi. 
Navbatdan 
elementni 
o„chirishda 
navbat 
boshi 
ko„rsatkichi 
ko„rsatayotgan adresdagi element o„chiriladi va shundan keyin bu ko„rsatkichning 
qiymati bittaga oshiriladi. Navbatga elementlar kiritilganda navbat oxiri 
ko„rsatkichi shu navbat uchun ajratilgan xotira sohasining oxiriga yetib qoladi. 
Bunda navbat to„lgan hisoblanadi.
Navbat boshi 
Navbat oxiri 
R=9 
chiqish 
kirish 

---

35 
Agar navbatdan elementlar o„chiriladigan bo„lsa, navbat boshida bo„sh joy 
ajratiladi. Vaholanki, navbat oxiri ko„rsatkichi chegaraga yetib qolganligi sababli, 
navbatga yangi element kiritib bo„lmaydi. Shu sababli navbatda har safar element 
o„chirilganda qolgan barcha elementlar bitta oldinga surilishi kerak bo„ladi. 
Natijada navbat oxirida bo„sh joy ochiladi. Bu holatda navbat boshi ko„rsatkichiga 
xojat qolmaydi. Lekin shuni aytish kerakki, bu yondashuv bir muncha noqulay 
hisoblanadi. Shuning uchun har safar elementlarni surib o„tirmaslik uchun navbatni 
halqasimon shaklda tashkil etamiz. Ya‟ni bunda xotirada navbat sohasining oxiriga 
yetib borilganda navbat boshiga o„tib ketiladi. Ushbu holatda navbat boshi va oxiri 
ko„rsatkichlari xotiradagi navbat sohasining boshini ko„rsatadi. Bu ikkala 
ko„rsatkichlarning tengligi navbatning bo„shligini anglatadi. Halqasimon navbatda 
element qo„shish amali o„chirish amalidan ko„proq bajarilsa, navbat oxiri 
ko„rsatkichi navbat boshi ko„rsatkichiga “yetib oladi”. Bu holat navbat to„laligini 
anglatadi. Halqasimon navbatda elementni o„chirish ikkala ko„rsatkich 
ko„rsatayotgan bitta adresda amalga oshiriladi. Bunday navbatning uzunligi boshi 
va oxiri ko„rsatkichlari farqi bilan aniqlanadi.