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

char Pop (Stack &S) {

if (S.size == 0 ) {

printf ("Stek bo’sh");

return char(255);

}

S.size --;

return S.data[S.size];

}

Pop funktsiyasi stek cho’qqisidan o’chirilgan belgini qaytaradi, shuning uchun ham stek o’lchami bir birlikka kamayadi. Agar stek bo’sh bo’lsa, funktsiya 255 kodi bilan belgini qaytaradi, ya’ni masala shartiga ko’ra stekda joylashishi mumkin bo’lmagan belgini qaytaradi va xatolik haqida xabar beriladi.

Misol. Satr ko’rinishidagi belgilarni kiriting, unda qavsning (), [] va {} shaklidagi uchta turi kiritilsin. Qavslarning to’g’ri qo’yilishini aniqlang (qavs ichidagi belgilarning ahamiyati yo’q). Masalan, satrda ()[{}] va [{}([])] kabi qavslar ketma-ketligi uchrasa to’g’ri, ([)] va ]]]((( kabi qavslar ketma-ketligi uchrasa noto’g’ri bo’ladi.

Qavsning bir xil turi uchun masalaning yechimi juda oson, ya’ni qavslarni juftligini hisobga oluvchi hisoblagich o’rnatamiz, satrni to’liq ko’rib chiqishda ochilgan qavs uchraganda hisoblagich bir birlikka oshiriladi, yopiluvchi qavs uchraganda bir birlikka kamaytiriladi. Agar hisoblagichlar dastur natijasida manfiy qiymat qabul qilmasa, to’g’ri, aks holda noto’g’ri qiymat qaytaradi.

Agarda qavsning bir necha turi ishtirok etsa, hisoblagich yordam bermaydi. Bunday masalaning yechimini olishning yagona va qulay yoo’li stek qoidasini qo’llash hisoblanadi. Boshida stek bo’sh deb qaraladi. Satr oxirini anglatuvchi kodi 0 bo’lgan belgigacha starni to’liq o’qiymiz. Agar ochiluvchi qavs uchrab qolsa, uni stekka joylashtiramiz. Agar yopiluvchi qavs uchrasa, uni stek cho’qqisiga joylashtiramiz, ya’ni uning ochiluvchi juftiga mos kelishi kerak. Agarda ushbu holat yuz bercha u holda stekni bo’shatamiz. Agar stek bo’sh yoki cho’qqisida boshqa turdagi qavs uchrab qolsa, ifodamiz noto’g’ri bo’ladi. Stekni o’qishning oxirida stek bo’sh bo’lishi shart.

Quyida oldin e’lon qilingan Stack tuzilmasi va Push va Pop amallari qo’llanilgan dastur keltirilgan.