Mavzu: Ma’lumotlarning yarim statik tuzilmalari Ma’ruza rejasi

Navbat

2.9-rasm. 4 ta elementdan iborat navbatning umumiy ko’rinishi

chiqish
kirish
Navbatni kompyuter xotirasida tashkillashtirish (joylashtirish) uchun elementlar soni chekli bo‘lgan bir o‘lchovli massivdan foydalanish mumkin. Bunda navbat elementlarining turi ko‘rsatilishi, uning boshi va oxiri uchun ikkita va oraliq ta‘minlashlar uchun yana bitta o‘zgaruvchi olinishi kerak.
Navbat tuzilmasi ustida bajariladigan amallar. Navbatlar uchun uchta amal aniqlangan:











insert (q,x) amali q navbatning oxiridan x elementni joylashtiradi;
remove(q) - q navbatning boshidagi element o‘chiriladi va u x o‘zgaruvchiga ta‘minlanadi;
empty(q) - amalida navbatning bo‘sh yoki bo‘sh emasligi tekshiriladi. Agar navbat bo‘sh bo‘lsa, true qiymat, bo‘sh bo‘lmasa, false qiymat hosil qilinadi.
Navbat tuzilmasi ustida bajariladigan amallar. Navbatlar uchun uchta amal aniqlangan:











Yarimstatik navbat bir o‘lchamli massiv orqali tashkillashtirilganda massivning to‘lib ketish holati bo‘lishi mumkin. Navbatning bunday holatini aniqlash uchun - full(q) amali qo‘llaniladi.
Insert amali navbatning barcha holatlarida (massivning to‘lib ketish holati bundan mustasno) bajarilishi mumkin.
Remove amali esa faqat bo‘sh bo‘lmagan navbat uchun qo‘llanilishi mumkin, chunki navbatda mavjud bo‘lmagan elementni o‘chirish mumkin emas. Empty amali har doim bajarilishi mumkin.
Dek










Inglizchada DEQ (Double Ended Queue) ikki tomonlama kirish-chiqishga ega bo‘lgan navbatni bildiradi. Dekning asosiy xususiyatlaridan biri - elementlarni yozish va o‘qish navbatning ikki tomonidan ham amalga oshirilishi mumkinligi.
chiqish kirish
kirish chiqish
Dekni quyi chegaralari orqali bog‘langan ikkita stek shaklda qarash mumkin. Buni temir yo‘l stantsiyasidagi vagonlar tuzilmasi sifatida qarash mumkin. Bu yerda yangi vagonni tuzilmaning yo bosh tomoni yoki oxiridan qo‘shish imkoniyati mavjud.