Mühazirə 1 Giriş Əsas anlayışlar. "Məlumat"

Mühazirə 5

Növbə
Elementlərin daxil edilməsi siyahının bir tərəfindən, xaric edilməsi digər tərəfindən aparılan dəyişən uzunluqlu ardıcıl xətti siyahıya növbə deyilir. Belə ki, burada birinci daxil edilən element birinci də xaric olunur. Bəzən növbəyə ingiliscə FİFO da deyilir.

Fiziki strukturu belədir. Yaddaşda yuxarı və aşağı sərhədləri təyin olunmuş sahə növbənin fiziki strukturudur.

Şəkil 2.3. Növbənin fiziki strukturu

Stekdən fərqli olaraq iki göstəricidən istifadə olunur. Biri elementlərin daxil olunması, digəri isə elementlərin xaric edilməsi üçündür. P₁- göstəricisi elementlərin daxil edilməsi, P₂- göstəricisi elementlərin xaric edilməsi üçün istifadə olunur.

Yeni elementin daxil edilməsi iki addımla aparılır.

1. 
   P₁ göstəricisi 1 slot artırılır. P₁ := P₁ + 1 ( slot )
   
2. 
   Həmin göstəriciyə görə yeni element növbəyə daxil edilir.
   

Növbədən elementin çıxarılması da iki addımla aparılır.

1. 
   P₂ göstəricisinə görə element növbədən çıxarılır.
   
2. 
   Göstəricinin qiyməti 1 slot artırılır. P₂ := P₂ + 1(slot)
   

Sonuncu alqoritmdən aydındır ki, element növbədən çıxarıldıqdan sonra o məntiqi silinmiş hesab olunur. Yeni elementin növbəyə daxil edilməsi zamanı əgər ( P₁ + 1 ) >= A_y olarsa, o zaman növbə dolub-daşmış hesab olunur. Növbənin sonu ilə əvvəlini əlaqələndirib dövrəli növbə adlanan struktur alındırmaqla dolub daşmanın qarşısını qismən almaq olar.

Şəkil 2.4. Dövrəvi növbənin fiziki strukturu

Adi növbədə

P₂≤ P₁ ; P₂= P₁+1

olur.

Dövrəvi növbədə isə aşağıdakı üç hal ola bilər.

P1>P2; P₁ =P₂ ; P1


Əgər dövrəvi növbə üzərində əməliyyat aparan zaman elementin növbəyə daxil edilmə əməliyyatlarının sayı elementin növbədən xaric edilmə əməliyyatlarının sayından çox olarsa, sonun göstəricisinin əvvəlin göstəricisini ötməsi vəziyyəti baş verə bilər. Bu vəziyyətdə növbə tam dolduğu halda göstəricilər müqayisə olunur və növbə dolu olduğu halda boş qeyd olunur.

Dövrəvi növbədə bu iki vəziyyəti -növbənin dolu və ya boş olması vəziyyətini fərqləndirmək etmək üçün sonun və əvvəlin göstəricisi arasında boş elementlərdən “aralıq” olmalıdır. Bu “aralıq “ 1 elementə kimi azaldıqda növbə tamamilə dolmuş olur və növbəyə yeni elementin daxil edilməsi mümkün olmur. Növbənin təmizlənməsi, boşalldılması isə hər iki göstəricinin ( başlanğıc olması vacib deyil ) eyni qiymət daşıdığı yazıda uzlaşır. Dövrəvi növbədə ölçünün təyin edilməsi göstəricilər fərqinin hesablanması ilə aparılır.

Növbədən kompüter resurslarının çatışmazlığı hallarında paralel yerinə yetirməli olan məsələləri, məsələn idarəetmə üçün istifadə olunur.

Dek
Dek(double ended queue) elə ardıcıl siyahıdır ki, elementlərin daxil və xaric edilməsi siyahının hər iki tərəfindən aparıla bilər. Dekin strukturunu aşağıdakı kimidir:

Şəkil 2.5. Dekin fiziki strukturu

Dek növbənin bir formasıdır, açıqlaması 2 sonluqlu növbə deməkdir. Növbədən fərqli - burada P₁ , P₂ həm giriş həm çıxış ola bilər. Növbədə daxil-xaric etmə haqqında qeyd edilənlər dekə də aiddir. Lakin bu zaman P₁ və P₂ – nin təyinatını nəzərə almaq lazımdır.

Dekin iki xüsusi halı ola bilər :

• 
  girişi məhdud dek
  
• 
  çıxışı məhdud dek
  

Girişi məhdud dekdə elementlərin daxil edilməsi yalnız bir sonluqdan, çıxışı məhdud olan dekdə isə elementlərin xaric edilməsi yalnız bir sonluqdan aparılır.