Muhammad Al-Xorazmiy nomidagi
Toshkent Axborot Texnologiyalar Universiteti
Farg‘ona filiali
“Dasturiy injiniringi” 850-22 guruh talabasi
Sodiqov Kamroning ning
Ma'lumotlar tuzilmasi va
algoritmlar fanidan
AMALIY MASHG’ULOT-10
Mavzu: Navbat tuzilmasi. Ro’yxatlar yordamida navbatni amalga oshirish.
Dek tuzilmasi. Asosiy operatsiyalar.
Ishdan maqsad. Ushbu laboratoriya ishida talabalar ro’yxatlar
yordamida
navbatni amalga oshirishni, talabalarSTL komponentlaridan biri bo’lgan
dek(deque) bilanishlashni o’rganishlari kerak.
Qo’yilgan masala. Talabalar topshiriq variantiga mos ravishda ro’xatlar
ustida
berilgan funksiyalar bilan ishlash ko’nikmasiga ega bo’lishlari kerak.
Ish tartibi:
•
Tajriba ishi nazariy ma’lumotlarini o‘rganish;
•
Berilgan topshiriqning algoritmini ishlab chiqish;
•
C++ dasturlash
muhitida dasturni yaratish;
•
Natijalarni tekshirish;
•
Hisobotni tayyorlash va topshirish.
Dek – bu ikki tomonlama navbat hisoblanadi. Ya’ni
(Double ended queues)
Ikkala uchli navbat - bu ikkala uchida kengayish va qisqarish xususiyatiga ega
bo'lgan ketma-ket konteynerlar.
Ular vektorlarga o'xshash, ammo elementlarni kiritish va yo'q qilishda samaraliroq.
Vektorlardan farqli o'laroq, tutashgan joy ajratilishini kafolatlash mumkin emas.
Dek, asosan ma'lumotlar tuzilmasining ikki tomonlama navbatini amalga
oshirishdir. Navbatdagi ma'lumotlar tuzilishi faqat oxiriga qo'shib, old tomondan
o'chirishga imkon beradi. Bu haqiqiy hayotdagi navbatga o'xshaydi, unda odamlar
old tomondan olib tashlanadi va orqada qo'shiladi. Ikkala tugagan navbat - bu
qo'shilish va o'chirish operatsiyalari ikkala uchida ham mumkin bo'lgan
navbatlarning alohida holati.
Dek uchun funktsiyalar vektor bilan bir xil,
oldinga va
orqaga surish va pop
operatsiyalari qo'shiladi.
Amaliy mashg’ulot topshirig’i:
Nazorat savollar
•
Navbat tuzilmasi qanday strukturaga ega?
•
Bog’langan ro’yxatda navbatni amalga oshirishni qanday kodlar
orqali amalga oshirish mumkin?
•
Dek ya’ni
(Double ended queues) nima va uning boshqa
konteynerlaridan farqi nima?
•
Dek uchun qaysi funksiyalar bilan bir xil,
oldinga va
orqaga
surish va
pop operatsiyalari qo'shiladi.
•
Deklarning vektorlar bilan asosiy farqi nimada?
1. **Navbat Tuzilmasi:**
Navbat (queue)
tuzilmasi, bitta to'plamning oxiridan (eng oxirgi
elementdan) kirib olinuvchi elementlar ro'yxatidir. Bu tuzilma FIFO (First-
In-First-Out) prinsipi asosida ishlaydi. Eng birinchi element ro'yxatga
qo'shiladi, eng oxirgi element esa ro'yxatdan olib tashlanadi. C++-da bu
tuzilma standart `queue` klassi orqali yaratiladi.
2. **Bog’langan Ro’yxatda Navbatni Amalga Oshirish:**
C++-da `queue` klassi orqali bog'langan ro'yxatda
navbatni amalga
oshirish uchun quyidagi kodi ishlatish mumkin:
```cpp
#include
#include
int main() {
std::queue myQueue;
// Navbatga element qo'shish
myQueue.push(10);
myQueue.push(20);
myQueue.push(30);
// Element olish va chiqarish
while (!myQueue.empty()) {
std::cout << "Element: " << myQueue.front() << std::endl;
myQueue.pop();
}
return 0;
}
```
3. **Dek (Double Ended Queue):**
Dek, iki tomonlama amalga oshirilishi mumkin bo'lgan ro'yxatdir. C++-da
`deque` klassi bilan ifodalangan.
Dekning asosiy xususiyati, bosh va
ohiridan element qo'shish va olishish imkoniyatiga ega bo'lganligidir.
4. **Dek
uchun bir xil, oldinga va orqaga surish va pop operatsiyalari:**
Dek (`deque`) uchun hamda `queue` uchun bir xil operatsiyalar bilan bir
xil, oldinga va orqaga surish va pop operatsiyalari amalga oshiriladi. Bu
funksiyalar `push_front()`, `push_back()`, `pop_front()` va `pop_back()`
metodlaridir.
```cpp
#include
#include
int main() {
std::deque myDeque;
// Oldinga va orqaga element qo'shish
myDeque.push_front(10);
myDeque.push_back(20);
myDeque.push_front(30);
// Elementlarni chiqarish
while (!myDeque.empty()) {
std::cout << "Element: " << myDeque.front() << std::endl;
myDeque.pop_front();
}
return 0;
}
```
5. **Deklarning Vektorlar Bilan Asosiy Farqi:**
Dek (`deque`) va vektor (`vector`) ham ikkala konteynerlar C++-dagi
to'plamlardir. Ular orasidagi farq esa boshqa. Vektor faqatgina o'z ichidagi
hajmini dinamik ravishda o'zgartiradi, lekin dek bosh va oxiridan
elementlarni qo'shish va olishish uchun o'zgaruvchilarga ega bo'lgan
