|
Mavzu:Steklar.Rekursiv protseduralar.
Oshxonadagi likopchalar turadigan quti, brovserning orqaga(“nazad”) tugmasi, ixtiyoriy matn muxarriridagi bekor qilish(“CTRL-Z”) amali, bularning barchasi Stek ma’lumotlar strukturasiga misoldir. “LIFO” y’ani oxirgi kegan birinchi ketadi qoidasi asosiga qurilgan bo’lib kompyuter olamida eng ko’p ishlatiladigan ma’lmumotlar strukturasidan biri. Demak, bugun Stek(Stack) ma’lumotlar strukturasini o’rganamiz.
Yuqoridagi rasmda stekning sodda ifodasi berilgan.
Rasmda ko’rinib turganidek, stek bu obyektlarning ro’yxati bo’lib, eng oxirgi qo’shilgan obyekt xar doim birinchi bo’lib qaytadi. Masalan, ushbu rasmdagi stekka yangi qiymat qo’shilsa A bitta pastga tushadi, yangi qo’shilgan obyekt “top” o’rinni egallaydi. Keyingi murojaat vaqtida aynan yangi qo’shilgan obyekt qaytariladi.
Ushbu ro’yxatda Stekning tarkibida bo’lgan operatsiyalar berilgan.
Push(value)stekka yangi qiymat qo’shadi. Aytib o’tilganidek, yangi qaiymat “top” o’ringa borib tushadi.
Pop()eng oxirgi qo’shilgan obyekt qaytariladi va stekdan o’chiriladi.
Peek()eng oxirgi qo’shilgan qaytariladi leki stekdan o’chirilmaydi.
IsEmpty()stek bo’shmi? degan savolga javobgar metod.
Size()stekdagi obyektlar sonini qaytaradi.
Stekning implementasiyasi ikki xil usulda bajarilishi mumkin. Zanjir(Linked) va Massiv. Ularning farqiga to’xtalib o’tamiz, lekin undan oldinIStackinterfacega diqqat qilamiz. Yuqorida berilgan amallarni kelajakda ushbu interfacedan meros olinadigan classlar uchun qoidaga aylantiramiz.
//Stek uchun iterface, T tipidagi obeyektlar bilan ishlaydi.
public interface IStack
{ /// Stack element qo'shish. /// /// Qo''shilishi lozim bo'lgan element.
void Push(T value);
/// Stackning boshidagi element o'chirib qiymatini qaytaradi. ///
T Pop();
/// Stackning boshidagi element qaytaradi, lekin o'chirmaydi.
T Peek();
/// Stack bo'shmi?
bool IsEmpty();
/// Stackdagi elementlar soni. ///
int Size();
}
Ro’yхаt – bu bеrilgаnlаrning kеtmа-kеt tаshkillаshtirilgаn strukturаsidir.Chiziqli ro’yхаtlаrning mаssivlаrdаn fаrqi shundаki, ulаr dаstur bаjаrilishi jаrаyonidа o’z хаjmini o’zgаrtirish imkоniyatigа egа. Binоbаrin ro’yхаtlаrning хаjmi оldindаn аniqlаnmаydi. Chiziqli ro’yхаtni zаnjir qismlаri ko’rinishidа tаsvirlаsh mumkin:
Ma’lumotlarning chiziqli tuzilmalari ro’yxatlar, cteklar, navbatlar va siklik ro’yxatlar deb ataluvchi turlarga bo’linadi. Ushbu ma’lumot tuzilmalari elementlari zanjir hosil qilib, har bir element ko’rsatkich yordamida o’zidan oldingi yoki o’zidan keyingi elementlarga ko’rsatadi. Ro’yxat boshidagi element head (bosh), oxiridagi element tail (dum) deb ataladi (1-rasm).
1-rasm. Ikki yo’nalishli ro’yxat.
Ro’yxatlar. Bunda to’g’ri to’rtburchaklar bilan ro’yxat elementlari ifodalangan. Elementlar ikki qismdan iborat: yozuv sohasi(ma’lumotlar) va adres sohasi. Adres sohasi keying yoki oldingi elementga murojaat ko’rsatkichini saqlaydi. Ro’yxatning barcha elementlariga murojaat qilish uchun ro’yxat boshi yoki oxirining adresi kifoya qiladi. Ro’yxatlar bir yo’nalishli va ikki yo’nalishli bo’lishi mumkin.
Steklar. “Oxirgi kelgan birinchi ketadi” (LIFO -Last In First Out), tamoyili asosida tashkil etilgan ro’yxatlar steklar deb ataladi. Stekda ixtiyoriy lementlarni o’chirish man qilinadi. Bu erda faqat oxirgi elementni o’chirishga ruxsat etiladi. Steklar quyidagi tarzda tashkil etiladi:
Stekning har bir elementi (birinchi elementdan tashqari) o’zidan oldingi elementga murojaatga ega bo’ladi;
– Stekka murojaat uchun oxirgi element adresi qo’llaniladi ( Tail);
– Yangi element stek oxiriga joylashtiriladi;
– Faqat oxirgi element o’chiriladi.
2-rasm. Stek
Navbatlar. “Oldin kelgan – oldin ketadi”. FIFO (First In First Out), tamoyili asosida tashkil etilgan ro’yxatlar navbatlar deb ataladi. Navbatda ixtiyoriy elementlarni o’chirish man etiladi. Faqat birinchi elementni o’chirishga ruxsat etiladi. Navbatning har bir elementi (oxirgi elementdan tashqari) o’zidan keyingi elementga murojaatga ega bo’ladi;
– Stekka murojaat uchun bosh (Head);va oxirgi element adresi qo’llaniladi (Tail);
– Yangi element navbat oxiriga joylashtiriladi;
– Faqat birinchi element o’chiriladi.
3-rasm. Navbat
Ikki yo’nalishli siklik ro’yxatlar. Ro’yxat oxirgi elementi birinchi elementga murojaat qilsa, bunday ro’yxatlar siklik deb ataladi. Siklik ro’yxatlar quidagi tarzda tashkil qilinadi:
Oxirgi element birinchi elementga murojaat etadi;
Po’yxat elemenlariga murojaat etish uchun oxirgi element (Tail) va birinchi element (Head) (shart emas)adresidan;
Yangi element ro’yxat oxiriga joylashtiriladi;
Elementni o’chirish kalit bo’yicha amalga oshiriladi (avval kalit bo’yicha izlash amalga oshiriladi).
Siklik ro’yxatlarga izlash va o’chirish algoritmlarini soddalashtirish imkonini beruvchi “soxta” element kiritish qabul qilingan.
4-rasm. Ikki yo’nalishli siklik ro’yxat
Do'stlaringiz bilan baham: | 
