2-laboratoriya ishi. Dinamik massiv, Stek, Navbat, Ro`yhat(bir tomonlama, ikki tomonlama), Lug`at ma`lumotlar strukturalarini mashina xotirasida

2-laboratoriya ishi. Dinamik massiv, Stek, Navbat, Ro`yhat(bir tomonlama, ikki tomonlama), Lug`at ma`lumotlar strukturalarini mashina xotirasida

“Yomon dasturchilar kod haqida o'ylashadi. Yaxshi dasturchilar esa ma'lumotlar strukturasi va ularning aloqalari haqida o'ylashadi. ”- Linus Torvalds, Linux yaratuvchisi.

Tez-tez muammolarni hal qilish yoki dasturlarni optimallashtirish uchun ishlatiladigan ma'lumotlar strukturasini tahlil qilamiz.

Stek. Stek nima va u qanday ishlaydi?

Stek – Stack inglizchadan uyum, g’aram, dasta, bog’lam degan ma’noni anglatadi.

Stek - bu LIFO (last in – first out; oxirgi kelgan – birinchi ketadi) prinsipi bo'yicha ishlaydigan ma'lumotlar strukturasi.

B
u juda aniq ta'rif, ammo yangi boshlanuvchilar uchun tushunish biroz qiyin bo'lishi mumkin. Shuning uchun, hayotning narsalar ko'rinishidagi to'plamni taqdim etish haqida to'xtalib o’taylik. Xayolga kelgan birinchi narsa - bu kitoblar to'plami ko'rinishidagi talqin, bu yerda eng yuqori kitob tepada joylashgan.

Aslida, stek har qanday narsaning to'plami sifatida ifodalanishi mumkin, u daftar, ruchka va shunga o'xshash narsalar to'plami bo'lishi mumkin, ammo kitoblar bilan misol eng maqbul bo'ladi.

Shunday qilib, stek nimadan iborat?

Stek katakchalardan iborat (masalan, bular kitoblar), ular ba'zi ma'lumotlarni o'z ichiga olgan tuzilish shaklida va ushbu strukturaning turiga keyingi elementga ko'rsatkich sifatida taqdim etiladi.

Stekka birinchi bo'lib kiritilgan element eng so'nggisi bo'ladi. Agar stekka uchta element qo'shsangiz, avval qo'shilgan oxirgi element o'chiriladi.

1-rasm
1-rasmda siz 6 ta raqamni ko'rishingiz mumkin: 6, 3, 8, 2, 4, 7. Shunga diqqat qilingki, biz ularni bir xil tartibda chiqaramiz. Masalan, 8 raqamini chiqarish uchun avval 6 va 3 raqamlarini, so'ngra 1 ni ajratib olishimiz kerak, chunki bu stek, biz bu raqamlarni teskari tartibda qo'shdik. Aniqroq qilib aytganda: 7, 4, 2, 8, 3, 6.

Stekda massivdagi kabi indekslar mavjud emas, demak ma'lum bir elementga murojaat qila olmaysiz. Buning sababi, stek bog'langan ro'yxatlar asosida tuzilgan. Bu shuni anglatadiki, har bir element (oxirgisidan tashqari - NULL-ga ishora qiladi, agar oddiy so'zlar bilan aytganda, hech narsaga ishora qilmasa) keyingi elementga ko'rsatgichga ega. Ammo ko'rsatgich bo'lmagan element mavjud - birinchisi (yoki uni bosh element deb ham atashadi).

Shu o’rinda savol paydo bo’lishi mumkin? Nima uchun massivlarni ishlatish mumkin bo’lganda stekni ishlatamiz.

Ammo shablonlar to'plamining butun go'zalligi elementlarni qo'shish va olib tashlashdan iborat. Ushbu amallar doimiy vaqt ichida amalga oshiriladi (bu yaxshi plyus).

Aytgancha, ba'zi dasturchilar massivda stek qilishadi. Stekdan foydalanishning bu usuli haqida biroz keyinroq gaplashamiz.