10-ma’ruza: navbat tuzilmalari: stek, navbat va dek reja

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.

const int MAXSIZE = 100;

struct Queue {

int data[MAXSIZE];

int size, head, tail;

};

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.