|
Ikki tomonlama navbat (deque, double-ended queue)
|
| bet | 37/143 | | Sana | 20.07.2024 | | Hajmi | 0,81 Mb. | | #268096 |
Bog'liq Tiplarni dinamik tarzda-fayllar.orgIkki tomonlama navbat (deque, double-ended queue). Deque – shunday maʻlumotlar tuzilmasiga aytiladiki, unda maʻlumotlarni qo‘shish va o‘chirish oldindan va orqadan amalga oshiriladi. Deque ham xuddi queue dek xotirada saqlanadi. Dek (Deque) bu shunday dinamik massivki, u ikki tomondan kengayishi va boshqa navbatlar va to‘plamlarga qaraganda tezroq.
Bundan tashqari, u har qanday holatda o‘zi elementlarni boshida yoki oxirida kiritish uchun ruxsat beradi, lekin o‘zboshimchalik holatda elementlarni tez kiritish imkoniyati saqlab qolinmasligi mumkin. Vektor o‘xshash amallari kam bo‘lishi mumkin.
Dek konteyner bilan tanishar ekanmiz u nimasi bilan yaxshi, boshqa konteynerlardan fanday farq qiladi degan savollar paydo bo‘lishi tabiiy albatta. Dekning umumiy tavsifidan boshlaymiz. STL da bu dek o‘zi nima? Tushuntirish uchun, uzoqqa bormaymiz, jismoniy tarbiya darsini olamiz. Ko‘pchiligimiz "bo‘y bo‘yicha saflanish" nimaligini bilamiz. Shunday qilib, haqiqiy Dek shunday qurilish mexanizmiga ega. Unda shunday bir qator hosil bo‘ladiki va bu qator uning oxirida va uning boshidan to‘ldiriladi, zarur bo‘lsa, bunda ketma-ket elementlarni o‘rnini almashtirishi ham mumkin. Qancha tezroq turish kerak bo‘lsa, shuncha yaxshi va stek, navbat maʻlumotlar tuzilmasiga qaraganda? Albatta, yo boshida yoki qatorning oxirida va qatorning o‘rtasida taxminan sizning bo‘y balandligiga qarash va keyin solishtirish va o‘rinlarni o‘zgartirish kerak. Biroq, bir
qator o‘rtasida joylashtirilgan bo‘lsa, butun elementlar suriladi. Bu hayotdan dekka qiyosiy misol edi.
Shakllantirilayotgan to‘plamning boshida yoki oxirida elementlarni qo‘shish kerak bo‘lganda, baʻzi elementlarni o‘rtaga qo‘yish kerak bo‘ladi dekni ishlatish mantiqan to‘g‘ri keladi (mos ravishda shu tipdagi dek tanlash kerak). Dekda ketma-ketlik o‘rtasida qo‘shish va o‘chirish qo‘llab-quvvatlash bo‘lsa-da, bu amallar chiziqli vaqtida amalga oshiriladi. Dasturda bu kabi amallar ko‘p bajarish kerak bo‘lsa, ro‘yxatlar eng yaxshi tanlov bo‘ladi.
Aslida, Dek-bu boshida yoki oxirida elementlarning tezroq qo‘shilishi imkoni bo‘lgan vektordir. Shu bilan birga, Dekning boshqa amallari vektorlarning tegishli amallari bilan bir xil ishlaydigan vaqtga (amallar ko‘naysa sekinroq) ega.
Dek ( navbat queue) bilan va vektor (vector) o‘rtasidagi farqlar:
Deklarning boshiga va oxiriga ham elementlarni qo‘shish tezkor amaldir, ammo vektorlar uchun faqat oxiriga qo‘shish tezkor amal hisoblanadi. Bu qo‘shish doimiy vaqt talab etadi.
Dekning funksiyalar va elementlarni qo‘shishga nisbattan vektordagi shunga o‘xshash funksiyalar odatda, bir oz sekin.
Dekning iteratorlari maxsus tipdagi aqlli ko‘rsatkichlarga ega bo‘lishi kerak, chunki doimiy ko‘rsatkichlar ular turli qismlari o‘rtasida biridan ikkinchisiga o‘tish kerak.
Xotira bloklari hajmiga chegaralari bor tizimlarida ikki tomonlama navbat dek xotirani ortiqg‘i bilan ajratadi, chunki vektor olishi mumkin bo‘lgan maʻlumotlarga nisbattan ko‘p. Shunday qilib, max_size () funksiyasining natijasi vektorlarga nisbatan ikki tomonlama navbatlarga katta bo‘lishi mumkin
Ikki tomonlama navbatlar imkoniyatlarni boshqarishni taʻminlamaydi va xotira qayta ajratilganda unga joy aniqlanmaydi. Xususan, boshida yoki oxirida elementlarni qo‘shish boshqa har qanday qo‘shish yoki o‘chirish kabi ikki tomonlama navbatda elementlar bilan bog‘liq barcha ko‘rsatkichlarni, murojaatlarni iteratorlar bekor qilmaydi. Biroq, xotiraning taqmislanishi vektorlarga qaraganda yaxshiroq ishlashi mumkin, chunki ular odatda ichki tuzilishiga ko‘ra, ikki tomonlama navbatlar xotirani qayta joylashtirishda barcha elementlarining nusxalash shart emas.
Deklarda ishlatilmaydigan xotira bloklari band qilinmaydi va real o‘lchamdan so‘ng xotiraning bo‘sh joylari ozod qilinadi. Buesa Dekning xotira hajmi kamaytirishga imkon beradi (ammo, qachon va qanday qilib bu sodir bo‘lshi uni amalga oshirishga bog‘liq).
|
| |
