Navbatdagi ma'lumotlar tuzilmasi

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.