KIRISH
Agar yarimstatik tuzilmani mantiqiy jihatdan qaraydigan bo‘lsak, u holda chiziqli ro‘yhat munosabati bilan bog‘langan ma’lumotlar ketma-ketligi tushuniladi. Xotirada yarimstatik ma’lumotlar tuzilmasini fizik jihatdan tasvirlaydigan bo‘lsak, bu xotirada slotlarning oddiy ketma-ketligidir, ya’ni har bir element xotirada navbatdagi slotlarda joylashadi. Yarimstatik MTni fizik tasvirlashning yana bir ko‘rinishi bir tomonlama bog‘langan ro‘yhat (zanjir) ko‘rinishida ifodalash mumkin, ya’ni bunda har bir navbatdagi elementning adresi joriy elementda ko‘rsatiladi. Bunday tasvirlashda tuzilmaning uzunligiga cheklanish unchalik qattiq qo‘yilmaydi. Bunday tuzilmalarga – navbat, stek, dek va satrlar kiradi.
Navbat bu FIFO (First In - First Out - "birinchi kelgan – birinchi ketadi"), shunday o‘zgaruvchan uzunlikdagi ketma-ketlik, ro‘yhatki, unda tuzilmaga elementlar faqat bir tomondan, ya’ni navbatning oxiridan qo‘shiladi va elementlarni tuzilmadan chiqarish boshqa tomondan, ya’ni navbat boshidan amalga oshiriladi. Navbat ustida bajariladigan asosiy amallar
yangi elementni qo‘shish,
elementni chiqarib tashlash,
uzunligini aniqlash,
navbatni tozalash.
Navbatni statik xotirada vektor ko‘rinishida ifodalashda 2 ta parametr, ya’ni navbat boshini (navbatning 1-elementini) va oxirini (navbatning oxirgi elementini) ko‘rsatuvchi ko‘rsatkichlar olinadi .
Navbatga yangi element kiritilayotganda navbat oxiri ko‘rsatkichi ko‘rsatayotgan adresga yoziladi va shundan keyin navbat oxiri ko‘rsatkichi bittaga oshiriladi. Navbatdan elementni o‘chirishda navbat boshi ko‘rsatkichi ko‘rsatayotgan adresdagi element o‘chiriladi va shundan keyin bu ko‘rsatkichning qiymati bittaga oshiriladi. Navbatga elementlar kiritilganda navbat oxiri ko‘rsatkichi shu navbat uchun ajratilgan xotira sohasining oxiriga yetib qoladi. Bunda navbat to‘lgan hisoblanadi.
Agar navbatdan elementlar o‘chiriladigan bo‘lsa, navbat boshida bo‘sh joy ajratiladi. Vaholanki, navbat oxiri ko‘rsatkichi chegaraga yetib qolganligi sababli, navbatga yangi element kiritib bo‘lmaydi. Shu sababli navbatda har safar element o‘chirilganda qolgan barcha elementlar bitta oldinga surilishi kerak bo‘ladi. Natijada navbat oxirida bo‘sh joy ochiladi. Bu holatda navbat boshi ko‘rsatkichiga xojat qolmaydi. Lekin shuni aytish kerakki, bu yondashuv bir muncha noqulay hisoblanadi. Shuning uchun har safar elementlarni surib o‘tirmaslik uchun navbatni halqasimon shaklda tashkil etamiz. Ya’ni bunda xotirada navbat sohasining oxiriga yetib borilganda navbat boshiga o‘tib ketiladi. Ushbu holatda navbat boshi va oxiri ko‘rsatkichlari xotiradagi navbat sohasining boshini ko‘rsatadi. Bu ikkala ko‘rsatkichlarning tengligi navbatning bo‘shligini anglatadi. Halqasimon navbatda element qo‘shish amali o‘chirish amalidan ko‘proq bajarilsa, navbat oxiri ko‘rsatkichi navbat boshi ko‘rsatkichiga “yetib oladi”. Bu holat navbat to‘laligini anglatadi. Halqasimon navbatda elementni o‘chirish ikkala ko‘rsatkich ko‘rsatayotgan bitta adresda amalga oshiriladi. Bunday navbatning uzunligi boshi va oxiri ko‘rsatkichlari farqi bilan aniqlanadi.
Tarixi
Stacks kompyuter fanlari adabiyotiga 1946 yilda, Alan M. Turing qo'ng'iroq qilish va subprogrammalardan qaytish vositasi sifatida "ko'mish" va "bury" atamalarini qo'llaganida kirdi. Subprogrammalar allaqachon 1945 yilda Konrad Zuzening Z4 - da joriy qilingan edi.
Myunxen Texnik Universitetidan Klaus Samelson va Fridrix L. Bauer 1955 yilda stek g'oyasini ilgari surdilar va 1957 yilda patent topshirdilar. 1988 yil mart oyida. Samelson vafot etganida, Bauer stek printsipini ixtiro qilgani uchun IEEE Computer Pioneer mukofotini oldi. Shunga oʻxshash tushunchalar mustaqil ravishda 1954 yilning birinchi yarmida Charlz Leonard Hamblin [ va 1958 yilda Vilgelm Kammerer tomonidan ishlab chiqilgan
Staklar ko'pincha kafeteryadagi prujinali plastinkalar to'plamining o'xshashligi yordamida tasvirlanadi. Toza plitalar stackning tepasiga joylashtiriladi va u erda mavjud bo'lganlarni pastga suradi. Plitani to'plamdan olib tashlanganda, uning ostidagisi yangi yuqori plastinka bo'lish uchun paydo bo'ladi.
STEK VA NAVBAT VA ULAR O'RTASIDAGI FARQ
Stek va Navbat ta’rifi.
Stack ta'rifi
Stek - bu ibtidoiy bo'lmagan chiziqli ma'lumotlar tuzilishi. Bu yangi element qo'shilgan va mavjud element faqat bitta uchidan o'chirilgan, bu to'plamning yuqori qismi (TOS) deb nomlangan buyurtma qilingan ro'yxat. Yig'indagi barcha o'chirish va qo'shish stackning yuqori qismidan amalga oshirilganligi sababli, oxirgi qo'shilgan element stackdan birinchi bo'lib olib tashlanadi. Shu sababli stack "Last-in-First-out (LIFO)" ro'yxat turi deb nomlanadi.
Stekka tez-tez kiradigan element eng yuqori element ekanligini, oxirgi mavjud element esa stakning pastki qismida joylashganligini unutmang.
Misol
Ba'zilaringiz pechene (yoki Poppins) yeyishingiz mumkin. Agar taxmin qilsangiz, qopqoqning faqat bir tomoni yirtilib, pechene birma-bir tashqariga chiqariladi. Bu "poping" deb nomlanadi va shunga o'xshash, agar siz birozdan keyin pechene saqlamoqchi bo'lsangiz, ularni xuddi shu yirtilgan uchi orqali paketga qaytarib qo'yasiz.
Navbat ta'rifi
Navbat - bu chiziqli ma'lumotlar tuzilishi, ibtidoiy bo'lmagan toifaga kiradi. Bu shunga o'xshash turdagi elementlarning to'plamidir. Yangi elementlarning qo'shilishi orqa uchi deb nomlangan bir uchida sodir bo'ladi. Xuddi shunday, mavjud elementlarni o'chirish Front-end deb nomlangan boshqa uchida ham amalga oshiriladi va bu mantiqan Birinchi bo'lib birinchi (FIFO) turidagi ro'yxatdir.
Misol
Bizning kundalik hayotimizda biz kerakli xizmatni kutish uchun kutadigan qatorlarga duch kelamiz, u erda biz o'zimizga xizmat ko'rsatish uchun navbat kutishimiz kerak. Ushbu kutish navbatini navbat deb hisoblash mumkin.
Stack va Queue ikkalasi ham ibtidoiy bo'lmagan ma'lumotlar tuzilmalari. Stek va quyruq o'rtasidagi asosiy farqlar shundan iboratki, ma'lumotlar to'plamiga kirish va qo'shilish uchun LIFO (birinchi navbatda oxirgi) usulidan foydalaniladi, navbat esa ma'lumotlar elementlariga kirish va qo'shilish uchun FIFO (Birinchi bo'lib birinchi chiqish) usulidan foydalanadi.
Stakda ma'lumotlar elementlarini surish va ochish uchun faqat bitta uchi bor, boshqa tomondan navbatda ma'lumotlar elementlarini siqish va dekektsiya qilish uchun ikkala uchi ham ochiq.
Stek va navbat ma'lumotlar bazasini saqlash uchun ishlatiladigan ma'lumotlar tuzilmalari bo'lib, ular aslida haqiqiy dunyo ekvivalentiga asoslanadi. Masalan, stek - bu CD-lar to'plami, u erda siz CD-lar to'plamining yuqori qismi orqali CD-ni chiqarib qo'yishingiz mumkin. Xuddi shunday, Navbat Teatr chiptalari uchun navbat bo'lib, u erda birinchi navbatda turgan odam, ya'ni navbatning oldida xizmat ko'rsatiladi va navbat kelgan yangi odam navbatning orqa qismida paydo bo'ladi (navbatning orqa uchi).
Dostları ilə paylaş: |
