O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI
“KOMPYUTER INJINIRINGI” FAKULTETI DI21-11 guruh talabasi Sharifov Bahriddin “Malumotlar tuzilmasi va algoritmlar”
Fanidan
2022-yil
Stek va Navbat
“Yomon dasturchilar o’zlarining kodlari haqida qayg’urishadi, yaxshi dasturchilar esa ma’lumotlar tuzilmalari va ularning bog’lanishlari haqida bosh qotirishadi.” — Linus Torvalds
III qism. Boshlang’ich ma’lumotlar tuzilmalari. 3-dars
O’tgan darsda sizlar bilan Array va Linked list haqida gaplashgan edik. Bu darsda ham boshlang’ich ma’lumotlar tuzilmalarini o’rganishda davom etamiz. Bugun sizlar bilan yana ikki ajoyib va eng keng qo’llaniladigan tuzilmalar bo’lgan Stack (Stek) va Queue (Navbat) haqida gaplashamiz.
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.
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
Image source: tutorialspoint.com
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
Image source: quora.com
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)
Shu bilan bugungi darsimizni yakunlaymiz va keyingi video darsimizda o’zimiz minimal funksiyali Stack va Queue yasashni ko’rib chiqamiz.
Maqolani sizga yoqqan bo’lsa unga qarsak (clap) chalib qo’yishni esdan chiqarmang. 50 tagacha qarsak chalish mumkin. Maqolani foydali deb hisoblasangiz uni do’stlaringizga ham ulashing! Bizning Telegram va YouTube kanallarimizga hamda mening Medium sahifamga obuna bo’ling.
