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

10-ma'ruza matni

10-MA’RUZA: NAVBAT TUZILMALARI: STEK, NAVBAT VA DEK 

Reja:

1. Stek va uning tadbiq qilish

2. Navbat va uning tadbiqi

3. Dek

4. Mustaqil ishlash uchun masalalar

5. Adabiyotlar 

Kalit so’zlari: stek, navbat, dek, LIFO (Last In - First Out), FIFO (First In - First Out), stek cho’qqisi. 

Saralavhada nomlari keltirilgan tuzilmalar (ya’ni, stek, navbat, dek) ham ro’yxat tuzilmasi hisoblanadi, lekin, bu tuzilmalarda elementlarni qo’shish yoki chiqarib tashlash bir tomonlama birinchi yoki oxirgi elementda amalga oshirilishi bilan farq qiladi.

1. Stek va uning tadbiq qilish

Stek — bu tartiblangan elementlar to’plami bo’lib, elementni qo’shish yoki mavjud elementni o’chirish faqat oxiridan, ya’ni stek cho’qqisi deb ataluvchi elementdan ruxsat beriladi.

Stek LIFO (Last In - First Out) – oxirgi kelgan birinchi ketadi turidagi tuzilma hisoblanadi. Stek bu likomchalar taxlamiga o’xshash tuzilma bo’lib, unda zarur bo’lgan likopchani olish uchun barchasini alohida ajratib chiqish, yoki yangi likopcha qo’yilishi kerak bo’lsa, u holda eng yuqoridagi likopcha ustida qo’yilishi talab etiladi. Rasmda 6 ta elementdan iborat stekka misol keltirilgan.

1-rasm. Stekning mantiqiy ko’rinishi

Zamonaviy kompyuterlarda stek quyidagi hollar uchun qo’llaniladi:

•      lokal o’zgaruvchilarni joylashtirish;

•      protsedura yoki funktsiyalarning parametrlarini joylashtirish;

•      qaytish adreslarini saqlashda (protseduradan qaysidir adresga qaytishda);

•      ma’lumotlarni vaqtinchalik saqlashda, asosan Assembler dasturlash tilida.

Stek uchun xotiraning cheklangan sohasi ajratiladi. Protseduraning har bir qayta chaqirilishida stekka yangi element qo’shiladi (parametrlar, lokal o’zgaruvchilar, qaytish adreslari). Shuning uchun ham protseduralarni aralash (tarkibli) chaqirish natijasida stek to’lib ketadi. Stekning to’lib ketishi rekursiv holatlarda juda xavfli hisoblanadi, ya’ni aynan protsedura yoki fnuktsiyani o’zini yoki tarkibini qayta chaqirish holatida yuz berishi mumkin. Agar tarkibli funktsiyani qayta chaqirish natijasida stek to’lib ketishi yuz bersa, dasturdagi rekursiya cheksiz bo’lib qolishi (tugallanmaydi) va xatolikka olib kelishi mumkin.