10-Маъруза: Steklar va navbatlar. Ularni mantiqiy tasvirlash va utida amallar bajarish algoritmi. 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.

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.