Stacklar Stack bu faqat bir tomondan o'zgartirilishi mumkin bo'lgan elementlar ro'yxati, stekning yuqori qismi

Stacklar

Stack - bu faqat bir tomondan o'zgartirilishi mumkin bo'lgan elementlar ro'yxati, stekning yuqori qismi deb ataladi .

Plitalar qo'yilgan plastinka dispenserini tasavvur qiling. Yangi plitalar faqat mavjud bo'lganlarning ustiga qo'shilishi mumkin va siz ularni faqat yuqoridan olishingiz mumkin. Shunday qilib, plastinka qoziqqa qanchalik kech qo'yilsa, u erdan tezroq olinadi. Ma'lumotlar tuzilmalari nuqtai nazaridan, bu LIFO printsipi deb ataladi (oxirgi kir, birinchi chiqadi).
Terminologiyadan foydalanish uchun stek o'zining yuqori qismidagi elementlarni qo'shish ( surish ) va olib tashlash ( pop ) operatsiyalarini qo'llab-quvvatlaydi .

Nega bekor qilish uchun stekdan foydalaniladi?
Chunki odatda biz oxirgi amalni bekor qilishni xohlaymiz. Stack uning yuqori qismiga elementlar qo'shish va oxirgi bo'lgan elementni olib tashlash imkonini beradi. Hech qanday harakat bekor qilinmasa nima bo'ladi? To'plam juda katta bo'ladi! To'g'ri. Agar siz bekor qilish to'plamidan elementlarni olib tashlamasangiz , ya'ni bekor qilish operatsiyasidan foydalanmasangiz, u juda katta bo'ladi. Shuning uchun Adobe Photoshop kabi ilovalar fayl ustida ishlaganda ko'proq operativ xotiradan foydalanadi. Bekor qilish to'plami faylda bajarilgan barcha amallarni siz faylni saqlaguncha va yopguningizcha xotirada saqlaydi.

Stackni amalga oshirish
Stack bog'langan ro'yxatlar yoki massivlar yordamida amalga oshirilishi mumkin. Men Python-da ikkala tuzilmada stekni amalga oshirishga misol keltiraman va har birining ijobiy va salbiy tomonlari haqida gapiraman.


Bog'langan ro'yxatdagi stack:


Стек на массиве:


Что лучше?
В коде я указал сложность каждой из операций, используя “О” большое. Как видите, имплементации мало чем отличаются.
Однако есть некоторые нюансы, которые стоит учесть.


massiv
Bu qo'shni xotira blokidir. Shu sababli, kichik stek hajmi bilan massiv qo'shimcha joy egallaydi. Yana bir kamchilik shundaki, siz har safar massiv hajmini oshirganingizda, barcha mavjud elementlarni yangi xotira joyiga nusxalashingiz kerak bo'ladi.
Bog'langan ro'yxat
U xotiradagi alohida bloklardan iborat va cheksiz o'sishi mumkin. Shuning uchun, bir tomondan, ushbu tuzilma yordamida stekni amalga oshirish algoritm murakkabligi nuqtai nazaridan biroz yaxshiroq . Boshqa tomondan, har bir element oldingi va keyingi elementning manzillarini saqlashi kerak, bu esa ko'proq xotirani talab qiladi .
Xulosa
Navbat to'ldirilishi bilan dinamik massiv ikki baravar ko'payganligi sababli, qo'shimcha xotira ajratish zarurati kamroq va kamroq bo'ladi. Bundan tashqari, ko'rsatkichlar ko'p joy egallamasligi sababli, bog'langan ro'yxatlardagi qo'shimcha ma'lumotlar muhim emas.
Ko'rib turganingizdek, stekning ushbu ikkita ilovasi o'rtasida deyarli hech qanday farq yo'q - o'zingizga yoqqanidan foydalaning.