Stack Stack bu yana bir chiziqli ma’lumot tuzilmasi bo’lib, u ham Linked listning maxsus bir ko’rinishi hisoblanadi. Stackda har bir tugunda ma’lumot va o’zidan oldingi tugun adresi saqlanadi. Shuning uchun unda faqat oxirgi qo’shilgan ma’lumot ustidagina qandaydir amal bajarish mumkin.
Ko’pchilikni “hayotini saqlab qolgan” CTRL+Z operatsiyasini ko’z oldingizga keltiring. Har safar bu tugmalarni bosganda oxirgi qilgan ishlaringiz orqadan oldinga qarab chiqib keladi (bekor qilinadi). Huddi shu yerda stack tuzilmasi ishlatilganini ko’rishimiz mumkin.
Stackga hayotiy misol sifatida bir uchi yopiq bo’lgan trubani keltirish mumkin. Trubaga do’stingiz bir nechta turli rangdagi sharlar tashladi. Endi siz sharlar rangini bilish uchun faqatgina do’stingiz oxirgi bo’lib truba ichiga tashlagan sharning ranginigina ko’ra olasiz. Qolgan sharlarni ko’rish uchun do’stingiz tashlagan tartibdan teskari tartibda ularni olib chiqishingiz kerak bo’ladi.
Rekursiv funksiyalar ham huddi shunday ishlaydi. Oxiriga yetmagan funksiyalar (return bo’lmagan) kelgan joyidan rekursiya stekiga tashlab ketilaveradi va keyin ular orqadan oldinga qarab bajariladi. Operatsiyalarning bunday ko’rinishda bajarilish jarayoni LIFO (Last In First Out) deb ataladi.
Stacklar bilan ishlashda doim eng oxirgi element adresi “esda saqlanadi” va bu element ko’pincha top deb ataladi.
Stack ustidagi asosiy amallar
Stackga element qo’shish (Push)
Stackdan elementni olish. Element o’chiriladi (Pop)
Stackdagi top elementni ko’rish. Element o’chirilmaydi (Peek)
Stackni bo’shlikka tekshirish (isEmpty)
Queue (Navbat) Queue ham Stack singari chiziqli ma’lumot tuzilmasi bo’lib, hayotdagi oddiy navbat singari ishlaydi. Shu sababli Stackdan farqli o’laroq Queueda eng oxirgi qo’shilgan elementga emas birinchi qo’shilgan elementga birinchi bo’lib “xizmat ko’rsatiladi”. Operatsiyalarni bunday ko’rinishda amalga oshirilishi esa FIFO (First In First Out) deb ataladi. Queueni tasavvur etish uchun quyidagi rasmning o’zi yetarli deb o’ylayman
Queuega dasturiy misollar sifatida printerga narsalarni chop qilishni uzatishni, yoki protsessor operatsiyalarni amalga oshirish jarayonini misol keltirish mumkin (protsessor ishlashi har doim ham FIFO ga asoslanmaydi). Yanayam qiziqrog’i hammamiz yoshligimizda (yoki hozir ham) o’ynashni yaxshi ko’rgan iloncha o’yinini Queuega misol qilish mumkin
Queueda biz ikkita tugun adresini xotirada saqlashimiz kerak bo’ladi. Navbat boshida turgan element uchun front, eng oxirgi element uchun rear yoki back.
Queue ustidagi asosiy amallar
Elementni navbat oxiriga qo’shish (Enqueue)
Elementni navbat boshidan chiqarib olish. Element o’chiriladi (Dequeue)
Navbat boshidagi elementni ko’rish. Element o’chirilmaydi (Peek)
Navbatni bo’shlikka tekshirish (isEmpty)
Stack vs Navbat Stack - bu tartiblangan ro'yxat bo'lib, unda ro'yxat elementlarini kiritish va o'chirish faqat yuqori deb nomlangan bir uchida amalga oshirilishi mumkin. Shu sababli, stack LIFO ma'lumotlarning oxirgi tuzilishi hisoblanadi. Navbat - bu buyurtma qilingan ro'yxat bo'lib, unda ro'yxat elementlari bir tomonda, orqa tomonda va o'chirish ikkinchi uchida amalga oshiriladi. Ushbu kiritish va o'chirish mexanizmi navbatni birinchi bo'lib birinchi bo'lib (FIFO) ma'lumotlar tuzilishiga aylantiradi.
Stack nima? Yuqorida aytib o'tilganidek, stack - bu ma'lumotlar strukturasi bo'lib, unda elementlar qo'shiladi va faqat bitta uchidan o'chiriladi. Steklar push va pop deb nomlangan ikkita asosiy operatsiyaga ruxsat beradi. Bosish operatsiyalari to'plamning yuqori qismiga yangi element qo'shadi. Qalqib chiquvchi operatsiya stekning yuqori qismidan elementni olib tashlaydi. Agar to'plam allaqachon to'lgan bo'lsa, surish operatsiyasi bajarilganda, bu to'plamning to'lib toshishi deb hisoblanadi. Agar pop -operatsiya allaqachon bo'sh to'plamda bajarilsa, u stack underflow sifatida qabul qilinadi. Stekada bajarilishi mumkin bo'lgan operatsiyalar sonining kamligi sababli, u cheklangan ma'lumotlar tuzilmasi hisoblanadi. Bundan tashqari, push va pop operatsiyalari ta'rifiga ko'ra, to'plamga oxirgi qo'shilgan elementlar birinchi bo'lib to'plamdan chiqib ketishi aniq. Shuning uchun stack LIFO ma'lumotlar tuzilmasi hisoblanadi.
Navbat nima? Navbatda elementlar navbatning orqa qismidan qo'shiladi va navbatning old qismidan chiqariladi. Birinchi navbatda qo'shilgan elementlar navbatdan o'chirilgandan so'ng, u FIFO tartibini saqlaydi. Elementlarni qo'shish va o'chirish tartibi tufayli navbat navbatdagi to'lov chizig'ini aks ettiradi. Navbat tomonidan qo'llab-quvvatlanadigan umumiy operatsiyalar navbat va navbatdan tashqari operatsiyalardir. Navbat navbatida ishlash navbatning orqa qismiga element qo'shadi, navbatni o'chirish esa navbatning old qismidagi elementni olib tashlaydi. Umuman olganda, navbatda xotira cheklovlaridan tashqari navbatga qo'shilishi mumkin bo'lgan elementlar soni cheklanmagan.
Stack va Queue o'rtasidagi farq nima? Steklar ham, navbatlar ham buyurtma qilingan ro'yxatlar turiga qaramay, ular bir -biridan muhim farqlarga ega. To'plamlarda, elementlarni qo'shish yoki o'chirish faqat yuqori deb nomlangan bir uchidan amalga oshirilishi mumkin, navbatda esa elementlarni qo'shish orqa tomondan, uchidan esa oldingi deb nomlanadi. Yig'ilishda, to'plamga oxirgi qo'shilgan narsalar birinchi navbatda to'plamdan chiqariladi. Shuning uchun stack LIFO ma'lumotlar tuzilmasi hisoblanadi. Navbatda birinchi navbatda qo'shilgan narsalar navbatdan o'chiriladi. Shuning uchun navbat FIFO ma'lumotlar tuzilmasi sifatida qaraladi.
