Navbatdagi ma'lumotlar tuzilmasi



Download 109,92 Kb.
Sana12.07.2022
Hajmi109,92 Kb.
#781793
Bog'liq
Navbat


Navbatdagi ma'lumotlar tuzilmasi
Ushbu qo'llanmada siz navbat nima ekanligini bilib olasiz. Shuningdek, siz C, C++, Java va Python tillarida navbatni amalga oshirishni topasiz.

Navbat - bu dasturlashda foydali ma'lumotlar tuzilmasi. Bu kino zalining tashqarisidagi chipta navbatiga o'xshaydi, bu erda navbatga birinchi kirgan odam chiptani birinchi bo'lib oladi.


Navbat “Birinchi kiruvchi birinchi chiqadi” (FIFO) qoidasiga amal qiladi – birinchi kirgan element birinchi chiqadi.



Yuqoridagi rasmda 1 2 dan oldin navbatda saqlanganligi sababli u ham navbatdan birinchi bo'lib o'chiriladi. U FIFO qoidasiga amal qiladi.

Dasturlash nuqtai nazaridan narsalarni navbatga qo'yish navbat, navbatdan narsalarni olib tashlash esa navbat deb ataladi.


Biz navbatni C, C++, Java, Python yoki C# kabi istalgan dasturlash tilida amalga oshirishimiz mumkin, ammo spetsifikatsiya deyarli bir xil.


Navbatning asosiy operatsiyalari
Navbat - bu quyidagi operatsiyalarni amalga oshirish imkonini beruvchi ob'ekt (mavhum ma'lumotlar strukturasi - ADT):

Navbat: Navbat oxiriga element qo'shing


Dequeue: Navbatning old qismidan elementni olib tashlang
IsEmpty: Navbat bo'sh yoki yo'qligini tekshiring
IsFull: Navbat to'lganligini tekshiring
Peek: Navbatning oldingi qiymatini olib tashlamasdan oling

Navbatning ishlashi


Navbat operatsiyalari quyidagicha ishlaydi:

ikkita ko'rsatkich OLD va ORQA


FRONT navbatning birinchi elementini kuzatib boradi
REAR navbatning oxirgi elementini kuzatib boradi
dastlab FRONT va REAR qiymatini -1 ga o'rnating

Navbatdagi operatsiya


navbat to'lganligini tekshiring
birinchi element uchun FRONT qiymatini 0 ga o'rnating
REAR indeksini 1 ga oshiring
REAR tomonidan ko'rsatilgan joyga yangi elementni qo'shing

Navbatdan chiqarish operatsiyasi


navbat bo'sh yoki yo'qligini tekshiring
FRONT tomonidan ko'rsatilgan qiymatni qaytaring
FRONT indeksini 1 ga oshiring
oxirgi element uchun FRONT va REAR qiymatlarini -1 ga tiklang



Navbat cheklovlari


Quyidagi rasmda ko‘rib turganingizdek, biroz navbat va navbat chiqarishdan so‘ng navbat hajmi kichraytirilgan.

Va biz 0 va 1 indekslarini faqat navbat qayta tiklanganda (barcha elementlar navbatdan chiqarilganda) qo'shishimiz mumkin.


REAR oxirgi indeksga yetgandan so'ng, bo'sh joylarga (0 va 1) qo'shimcha elementlarni saqlashimiz mumkin bo'lsa, biz bo'sh joylardan foydalanishimiz mumkin. Bu dumaloq navbat deb ataladigan o'zgartirilgan navbat tomonidan amalga oshiriladi.


Murakkablik tahlili


Massiv yordamida navbatdagi navbat va navbatdan chiqarish operatsiyalarining murakkabligi O(1) ga teng. Agar siz python kodida pop (N) dan foydalansangiz, unda murakkablik ochiladigan elementning holatiga qarab O (n) bo'lishi mumkin.

Navbat ilovalari


CPU rejalashtirish, Disk rejalashtirish
Ma'lumotlar ikki jarayon o'rtasida asinxron ravishda uzatilganda. Navbat sinxronizatsiya uchun ishlatiladi. Masalan: IO buferlari, quvurlar, IO fayli va boshqalar
Haqiqiy vaqt tizimlarida uzilishlarni boshqarish.
Qo'ng'iroqlar markazining telefon tizimlari odamlarni ularni tartibda ushlab turish uchun navbatlardan foydalanadi.
Download 109,92 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish