Ikki tomonlama navbat (deque, double-ended queue)

Download 1,92 Mb.
bet	34/131
Sana	16.06.2024
Hajmi	1,92 Mb.
	#264063

1 ... 30 31 32 33 34 35 36 37 ... 131

Bog'liq
Tiplarni dinamik tarzda

Ikki 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).

Dekka taʻluqli bo‘lgan vektorlarning afzalligi.

To‘plamning o‘rtasida elementlarni qo‘shish va o‘chirish sekinroq amal hisoblanadi. Chunki bir o‘zgarish uchun barcha elementlarning o‘rinlarini almashtirish kerak bo‘ladi.
Vektorlar va deklarning iteratorlari erkin ruxsat turiga mansub.
Dek sinfi vektor sinfining funksiyalari bilan bir xil funksiyalarga ega. Dekning kamchiliklariga

Tez-tez qo‘shish yoki o‘chirish dekning boshida yoki oxirida sodir bo‘lishi.
Konteyner elementlariga havola qilaolmaysiz.
Konteyner ishlatilmay qolganda xotirani xoli qilish amalga oshirilishiga C++ qafolat bermaydi (amalga oshirish tamoyiliga qarab, xoli bo‘lshi va bo‘lmasligi ham mumkin)

Inobatga olishini kerak bo‘lgan holatlar:

Dekning at() boo‘qa biror bir funksiyasi iterator va indeksni tekshira olmaydi.
Qo‘shish va o‘chirish qo‘shimcha xotira talab qilish mumkin. Shuning uchun qo‘shish va o‘chirishga doir amallar bajarilganda dekning boshqa elementlari uchun ko‘rsatkichlar, havolalar va iteratorlarni aniq ko‘rsata olmaydi. Bunga istisno bo‘lib, Dekning boshiga yoki oxiriga element qo‘shish olinadi. Boshiga yoki oxiriga qo‘shilganda ko‘rsatkich va havolalar aniq bo‘ladi, ammo iterator yo‘q.
Dek va vektorning interfeyslari deyarli bir xil. Farqi shundaki, baʻzi bir funksiyalash yaratilgan bo‘lishi mumkin. Masalan, dek sinfi capacity, reserve kabi funksiyalarga ega emas. Buning sababi dek vektorlarga o‘xshab ishlashini yaxshilash kerak emas.
Deklar bilan ishlaganda, ayniqsa maʻlumotlarni qo‘shishda ko‘rsatkich va iteratorlarga bohliq dastur fragmenini yozishdan ehtiyot bo‘lish va mustaqil yozish kerakmas.

Umuman olganda, shaxsiy deklar bu vektorlardir, ular bilan ishlash ham vektorlar kabi amalga oshiriladi. Ammo qachon dekni, qachon vektorni tanlashni bilish kerak.
Maʻlumotlar tuzilmasining boshiga va oxiriga qo‘shish uchun optimizatsiyalangan (yaxshilangan, ixcham qilingan) vektor – bu dekdir. Bunda qo‘shish aniq o‘zgarmas vaqtda bajariladi va nusxalash konstruktorini bir marta chaqiradi.
Agar element dekning o‘rtasiga qo‘shilsa, eng yomoni bu amal vaqt talab qiladi, chunki qo‘shish nuqtadan boshigacha va oxirigacha bo‘lgan masofalar orasida kichik aniqlash lozim.
insert, push_front i push_back funksiyalari dekdagi hamma iteratorlarni bekor qilishi mumkin. Shuningdek dekning o‘rtasiga maʻlumot qo‘shilganda havolalarni xam bekor qiladi.
Berilgan navbatdagi elementlarni guruhlash masalasini qaraylik. Guruhlashni amalga oshirish uchun guruhlash shartini tanlaymiz va shu asosida navbat ichida guruhlaymiz, shartga tegishli bo‘lganlar navbat boshidan, bo‘lmaganlar oxiridan joylatiriladi.
4.8-dastur. Navbvtdagi elementlarni guruhlash.

// Created by MBBahodir #include "stdafx.h" #include #include #include using namespace std;

bool mypred(const int x){

return x <= 51; // guruhlash uchun shart
}

int main(){

int Arr[]={1,78,89,23,51,49,100,18,50};
deque d(&Arr[0],&Arr[9]);
cout << "Joriy deque: " << endl;
for (deque::iterator it=d.begin();it!=d.end();it++) std::cout<<*it<<" | "; cout << endl;
stable_partition(d.begin(),d.end(),mypred);
cout << "Natija: " << endl;
for (deque::iterator it=d.begin();it!=d.end();it++) std::cout<<*it<<" | "; cout << endl;
system("pause"); return 0;
}

4.8-dastur.Output

Joriy deque:
1 | 78 | 89 | 23 | 51 | 49 | 100 | 18 | 50 | Natija:
1 | 23 | 51 | 49 | 18 | 50 | 78 | 89 | 100 |

4.7-dasturdagi fragment asosiy guruhlash sharti hisoblanadi.

bool mypred(const int x){
return x <= 51; // guruhlash uchun shart
}

Bunda agar x <= 51 bo‘lsa true, aks holda flase qaytaradi. Bunga ekvivalent sifatida quyidagicha fragment ham yozish mumkin.

bool mypred(const int x){
if (x <= 51) return true; // guruhlash uchun shart return false;
}

Dek uchun keltirilgan materiallar dastlabki o‘rganuvchilar uchun yetarli deb hisoblaymiz. Masalaning shartiga qarab dek yoki vektorni tanlash dasturchining mahoratiga bog‘liq.
Dekning funksiyalariga quyidagilar kiradi:
4.1-jadval. Dekning funksiyalari

push_front	Boshidan yangi element qo‘shish
push_back	Oxiridan yangi element qo‘shish
pop_front	Birinchi elementni olish
pop_back	Oxirgi elementni olish
front	Birinchi element qiymatini ko‘rish
back	Oxirgi element qiymatini ko‘rish
size	Elementlar sonini ko‘rish
clear	Barcha elementlarni o‘chirish

Download 1,92 Mb.

1 ... 30 31 32 33 34 35 36 37 ... 131

Download 1,92 Mb.