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

2-tajriba ishi. YARIMSTATIK MA‟LUMOTLAR TUZILMASI 
Ishdan maqsad: Navbat, stek va dekni o„rganish hamda ularni tadqiq qilish. 
Yarimstatik ma‟lumotlar tuzilmalari ustida amal bajarish algoritmlarini o„rganish. 
Qo„yilgan masala: C++ tilida navbat, stek va dekni statik ko„rinishda e‟lon 
qilish va topshiriq variantiga ko„ra uning ustida amal bajarish dasturini ishlab 
chiqish. 
Ish tartibi: 
 Tajriba ishi nazariy ma‟lumotlarini o„rganish; 
 Berilgan topshiriqning algoritmini ishlab chiqish; 
 C++ dasturlash muhitida dasturni yaratish; 
 Natijalarni tekshirish; 
 Hisobotni tayyorlash va topshirish. 
 
2.1. Yarimstatik ma‟lumotlar tuzilmasi 
Yarimstatik ma‟lumotlar tuzilmasini quyidagicha tavsiflash mumkin:
- o„zgaruvchan uzunlikka ega va uni o„zgartiruvchi oddiy funksiyalariga 
ega; 
- tuzilmaning uzunligini o„zgartirish ma‟lum bir chegarada, ya‟ni qandaydir 
bir maksimal qiymatdan oshmagan holda amalga oshirilishi mumkin; 
Agar yarimstatik tuzilmani mantiqiy jihatdan qaraydigan bo„lsak, u holda 
chiziqli ro„yhat munosabati bilan bog„langan ma‟lumotlar ketma-ketligi 
tushuniladi. Xotirada yarimstatik ma‟lumotlar tuzilmasini fizik jihatdan 
tasvirlaydigan bo„lsak, bu xotirada slotlarning oddiy ketma-ketligidir, ya‟ni har bir 
element xotirada navbatdagi slotlarda joylashadi. Yarimstatik MTni fizik 
tasvirlashning yana bir ko„rinishi bir tomonlama bog„langan ro„yhat (zanjir) 
ko„rinishida ifodalash mumkin, ya‟ni bunda har bir navbatdagi elementning adresi 
joriy elementda ko„rsatiladi. Bunday tasvirlashda tuzilmaning uzunligiga

---

34 
cheklanish unchalik qattiq qo„yilmaydi. Bunday tuzilmalarga – navbat, stek, 
dek va satrlar kiradi.
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.