Guruch. 1.1.2.1 Ikki marta bog'langan ro'yxat elementini o'chirish
Navbat - "birinchi kiruvchi - birinchi chiqadi" (FIFO, birinchi kiruvchi - birinchi chiqadi) elementlarga kirish intizomiga ega ma'lumotlar strukturasi. Elementni qo'shish (odatda enqueue - navbatga qo'yish so'zi bilan belgilanadi) faqat navbat oxirida, tanlash - faqat navbat boshidan mumkin, tanlangan element navbatdan olib tashlanadi. Dasturlash tillarida navbatni amalga oshirishning bir necha usullari mavjud. 2.1.1 Massiv Birinchi usul navbatni massiv va ikkita butun o'zgaruvchining boshlanishi va tugashi sifatida ifodalaydi. Odatda boshlang'ich navbatning boshiga, oxiri esa navbatga yangi element kirganda to'ldiriladigan elementga ishora qiladi. Navbatga element qo'shilganda, navbatning yangi elementi q[end] ga yoziladi va end bittaga kamayadi. Agar end qiymati 1 dan kichik bo'lsa, biz massiv atrofida aylanamiz va o'zgaruvchining qiymati n ga teng bo'ladi. Navbatdan elementni olib tashlash ham xuddi shunday tarzda amalga oshiriladi: q [start] elementi navbatdan olib tashlangandan so‘ng start o‘zgaruvchisi 1 ga kamayadi. Bunday algoritmlarda n dan bitta katak har doim bo‘sh bo‘ladi (chunki a n elementli navbatni bo'shdan ajratib bo'lmaydi), bu algoritmlarning soddaligi bilan qoplanadi. Ushbu usulning afzalliklari: ikkinchi usul bilan solishtirganda xotirani biroz tejash mumkin; rivojlantirish osonroq. Kamchiliklari: Navbatdagi elementlarning maksimal soni massiv hajmi bilan chegaralanadi. U to'lib ketganda, u xotirani qayta taqsimlashni va barcha elementlarni yangi massivga nusxalashni talab qiladi. 2.1.2 Bog'langan ro'yxat Ikkinchi usul dinamik xotira bilan ishlashga asoslangan. Navbat chiziqli ro'yxat sifatida ifodalanadi, unda elementlarni qo'shish/o'chirish qat'iy ravishda uning tegishli uchlaridan kelib chiqadi.
Do'stlaringiz bilan baham: |
