Dek so‘zi (deq double Ended Queue) ingliz tilidan olingan bo‘lib 2 ta chetga EGA navbat degan ma’noni bildiradi

Ibraimov Shohjaxon

Deque
Mustaqil ish

Dek so‘zi (DEQ - Double Ended Queue) ingliz tilidan olingan bo‘lib 2 ta chetga ega navbat degan ma’noni bildiradi.

Ikki tomonlama navbatlar - bu ikkala uchida kengayish va qisqarish xususiyatiga ega bo'lgan ketma-ket konteynerlar . Ular vektorlarga o'xshaydi, lekin elementlarni kiritish va o'chirishda samaraliroq. Vektorlardan farqli o'laroq, qo'shni saqlashni ajratish kafolatlanmasligi mumkin.
Ikki tomonlama navbatlar asosan ma'lumotlar strukturasining ikki tomonlama navbatini amalga oshirishdir. Navbatdagi ma'lumotlar strukturasi faqat oxirida kiritish va old tomondan o'chirish imkonini beradi. Bu haqiqiy hayotdagi navbatga o'xshaydi, unda odamlar old tomondan olib tashlanadi va orqaga qo'shiladi. Ikki tomonlama navbatlar - bu ikkala uchida ham kiritish va o'chirish operatsiyalari mumkin bo'lgan navbatlarning alohida holati.
Deque uchun funktsiyalar vektor bilan bir xil, front va back uchun push va pop operatsiyalari qo'shilishi bilan.
Deklar ustida turli operatsiyalarni bajarish uchun vaqt murakkabligi quyidagilardir:
Elementlarga kirish - O(1)
Elementlarni kiritish yoki olib tashlash - O(N)
Boshida yoki oxirida elementlarni kiritish yoki olib tashlash - O(1)
push_front() - elementlarni old tomondan dekkaga surish uchun ishlatiladi.
push_back() - bu funksiya elementlarni orqa tomondan dekkaga surish uchun ishlatiladi.
pop_back() - funktsiyasi old tomondan dequedan elementlarni chiqarish yoki olib tashlash uchun ishlatiladi.
pop_front() - funksiyasi orqa tomondan dequedan elementlarni chiqarish yoki olib tashlash uchun ishlatiladi.
front() - funktsiyasi deque konteynerining birinchi elementiga murojaat qilish uchun ishlatiladi.
back() - funktsiyasi deque konteynerining oxirgi elementiga murojaat qilish uchun ishlatiladi.
empty() - funktsiyasi deque konteynerining bo'sh yoki bo'shligini tekshirish uchun ishlatiladi.
size() - funksiyasi deque konteynerining hajmini yoki deque konteyneridagi elementlar sonini qaytarish uchun ishlatiladi.
Dequega elementlarni kiritish.
Elementlarni kiritish uchun quyidagi usullardan foydalanishimiz mumkin:
push_back()- oxiriga elementlarni kiriting.
push_front()- elementlarni boshida kiriting
Masalan,


#include
#include
using namespace std;
int main() {
deque nums {2, 3};
cout << "Boshlangich Deque: ";
for (const int& num : nums) {
cout << num << ", ";
}
// oxiriga 4 sonini qoshamiz
nums.push_back(4);
// old tomondan 1 sonini qoshamiz
nums.push_front(1);
cout << "\nOzgargan Deque: ";
for (const int& num : nums) {
cout << num << ", ";
}
return 0;
}
Dastlabki deque: 2, 3,
Yakuniy deque: 1, 2, 3, 4,
Deque ma'lumotlar tuzilishi


Muayyan kutubxonalar dequesni turli yo'llar bilan amalga oshirishi mumkin, odatda dinamik massivning qandaydir shakli sifatida. Lekin har qanday holatda ham, ular alohida elementlarga to'g'ridan-to'g'ri tasodifiy kirish iteratorlari orqali kirishga imkon beradi, kerak bo'lganda konteynerni kengaytirish va qisqartirish orqali saqlash avtomatik ravishda boshqariladi. 
Shuning uchun ular vektorlarga o'xshash funksionallikni ta'minlaydi, lekin ketma-ketlikning boshida emas, balki faqat oxirida elementlarni samarali kiritish va o'chirish bilan. Ammo, vektorlardan farqli o'laroq , deklar uning barcha elementlarini qo'shni saqlash joylarida saqlashi kafolatlanmaydi: dequeko'rsatgichni boshqa elementga siljitish orqali a dagi elementlarga kirish aniqlanmagan xatti-harakatlarga olib keladi .
Ikkala vektorva deques juda o'xshash interfeysni ta'minlaydi va shunga o'xshash maqsadlarda ishlatilishi mumkin, lekin ichkarida ikkalasi ham butunlay boshqacha yo'llar bilan ishlaydi: Vektorlar o'sish uchun vaqti-vaqti bilan qayta taqsimlanishi kerak bo'lgan bitta massivdan foydalansa-da, deque elementlari turli bo'laklarga tarqalishi mumkin. Doimiy vaqtda va bir xil ketma-ket interfeysga ega (iteratorlar orqali) uning har qanday elementiga to'g'ridan-to'g'ri kirishni ta'minlash uchun kerakli ma'lumotni ichida saqlaydigan konteyner bilan saqlash. Shuning uchun, deklar vektorlarga qaraganda ichki jihatdan biroz murakkabroqdir , lekin bu ularga ma'lum sharoitlarda, ayniqsa, qayta taqsimlash qimmatroq bo'lgan juda uzoq ketma-ketliklarda samaraliroq o'sishga imkon beradi.
Deque dan elementlarga kirish
Dequening elementlariga kirish uchun quyidagi usullardan foydalanishimiz mumkin deque:
front()- oldingi elementni qaytaradi
back()- orqadagi elementni qaytaradi
at()- belgilangan indeksdagi elementni qaytaradi
Masalan,
#include
#include
using namespace std;
int main() {
deque nums {1, 2, 3};
cout << "Old element: " << nums.front() << endl;
cout << "Oxirgi element: " << nums.back() << endl;
cout << "Elementning indexsi 1: " << nums.at(1) << endl;
cout << "Elementning indexsi 0: " << nums[0];
return 0;}
Natija:
Old element: 1.
Orqa element: 3.
1: 2 indeksidagi element.
0:1 indeksidagi element.
Operatordan deque elementlariga kirish uchun foydalanishimiz mumkin bo'lsa-da [], usuldan foydalanish afzalroqdir at().
Buning sababi, at()deque chegaradan tashqarida bo'lganda istisno qiladi va []axlat qiymatini beradi.
Dequeni amalga oshirish juda oddiy va oddiy navbatga o'xshaydi, faqat old tomondan kiritish va oxirida o'chirish uchun ikkita qo'shimcha funktsiyani yozishingiz kerak, shuningdek, bir nechta shartlarni biroz o'zgartirishingiz kerak bo'lishi mumkin. Shuningdek, biz dumaloq navbat yordamida dequeni amalga oshirishimiz mumkin, bu esa uni yanada samaraliroq qiladi.
Standart shablonlar kutubxonasida biz odatda deque dan foydalanamiz, chunki u samarali va juda ko'p ajoyib o'rnatilgan funktsiyalarga ega, siz o'zingizni ko'rishingiz mumkin, deque oddiy navbatga qaraganda ancha ko'p funktsiyalar bilan jihozlangan.
Iteratorlar:

•