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

Mühazirə 4

Xətti yarımstatik strukturlar.Əsas anlayışlar. Stek.

Yarımstatik strukturlarda elementlərin sayı qabaqcadan təyin olunan müəyyən sərhəd çərçivəsində dəyişə bilər, əlaqələr isə elementlər arasında adətən xətti ardıcıl olur. Struktur üçün əvvəlcədən ayrılan yaddaş sahəsinin ölçüsü ilə fiziki strukturda elementlərin sayına qoyulan məhdudluq müəyyən olunur.

Stack deyildikdə bir tərəfli giriş və çıxışlara malik olan ADT (Abstract Data Type) nümunəsi başa düşülür. Digər strukturlardan fərqli olaraq Stack nümunəsi üçün LİFO(Last in First out) qanunu ödənilir. Bunun məğzi ondan ibarətdir ki, yığına sonuncu əlavə olunan element birinci yerdə dayanır və yığın üzərində əməliyyat aparılarkən (məs. Pop() funksiyası) sonuncu əlavə olunmuş elementdən başlanılır. Yarımstatik strukturlara aiddir: stek, növbə və dek. Qeyd edək ki, göstərilən bu strukturlara yarımstatik struktur kimi baxılması şərti xarakter daşıyır. Bu strukturların dinamik variantlarını da qurmaq mümkündür. Belə olan halda strukturun elementlərinin sayına məhdudluq qoyulmur və əlaqələndirilmiş siyahı strukturlarında olduğu kimi, elementlər bir-birilə göstəricilər vasitəsilə əlaqələndirilir.

Elementlərin daxil olunması və onların xaric edilməsi ancaq siyahının bir tərəfindən aparılan dəyişən uzunluqlu ardıcıl siyahıya stek deyilir. Belə strukturda sonuncu daxil olunan element birinci xaric olunur.

Stek elementləri eyni tipli skalyar kəmiyyət ,eləcə də sabit uzunluqlu yazı ola bilər. Elementlərin daxil və xaric edilməsi prosesi stekin təpəsindən aparılır. Stekin təpəsi xüsusi göstərici ilə ünvanlaşdırılır.

Şəkil 2.1. Stekin ümumi strukturu

yuxarı sərhəddi aşarsa, onda “ dolub-daşma “ siqnalı hasil

edilir.

Alqoritmin təsviri.

1. 
   Göstəricinin yuxarı sürüşdürülməsi.
   

P_s := P_s + L ;

2. 
   Daşmanın yoxlanması.
   

Əgər P_s > A_y olarsa, onda “dolub-daşma“ siqnalı hasil edib alqoritmi bitirməli.

3. 
   Yeni elementin stekə yazılması.
   

X – E { P_s }

Yeni elementi Ps göstəricisinə uyğun sahəyə yazıb alqoritmi bitirməli.

Stekdən elementin xaric edilməsi ( SXAR alqoritmi ) :

İlk növbədə stekin boş olub-olmaması yoxlanır. Əgər stek boş olarsa, lazım olunan siqnal hasil olunur. Əks halda isə göstəricinin ünvanlaşdırdığı element işçi sahəyə ( İS ) köçürülür və göstərici bir slot yəni, bir elementin uzunluğu (L) qədər “aşağı“ sürüşdürülür.

Alqoritmin təsviri.

1. 
   Stek boşdur. Əgər P_s < A_a onda stekin boş olması haqqında məlumat çap edib alqoritmi bitirməli.
   
2. 
   Stekdən elementin xaric olunması.
   

E { Ps } – İS

P_s göstəricisinə uyğun olan element işçi sahəyə yazılır.

3. 
   Göstəricinin dəyişdirilməsi.
   

P_s := A_y – L

qəbul edib alqoritmi bitirməli.

Yığından söhbət gedərkən ilk olaraq təməlində 3 əsas funksiyanın olmasını qeyd etmək lazımdır. Stack’in işlədilə bilinməsi bu funksiyalar sayəsində mümkün olur. Bunları aşağıdaki formada qruplaşdırmaq olar:

Push() – Stack’in içərisinə dəyər daxil etmək üçün istifadə olunur;

Pop() – Stack’in içərisindən mövcud dəyəri götürmək üçün istifadə olunur;

Top() – Stack’in təpə nöqtəsindəki dəyəri almaq üçün istifadə olunur;

Onuda qeyd edək ki, Push() və Pop() funksiyaları LİFO qanununa uyğun şəkildə müvafiq olaraq Stack’in təpə nöqtəsinə dəyər əlavə edir və götürür. Top() funksiyası isə dəyəri Stack’dən çıxartmır onu sadəcə oxuyur.

Aşağıdaki şəkildə Stack’in quruluşu vizual olaraq təsvir olunmuşdur.

Stack’lər bir qayda olaraq ya Massivlər(Arrays) yada Əlaqəli Siyahılar (Linked Lists) üzərində qurulurlar. Bu laboratoriya işi çərçivəsində həm Massivlər həmdə Əlaqəli Siyahılar vasitəsilə Stack strukturları inşa edəcək və bu strukturlar üzərində Push(), Pop() və Top() funksiyalarını icra edəcəyik.

Kodlaşdırmaya keçməzdən əvvəl onuda qeyd edək ki, Stack strukturlarını massivlərin köməyi ilə qurmaq əslində praktikada o qədər də təsadüf olunan məsələ deyil. Sonradan kodda da görəcəyimiz kimi, məsələn 4 elementə sahib bir massivə 5.ci elementi əlavə etmək lazım gəldikdə bu massivdən iki dəfə böyük olan başqa bir massiv yaradılır və əvvəlki massivin elementləri yeni massivə kopyalandıqdan sonra massivə son olaraq yeni element əlavə olunur. Buradan göründüyü kimi bu üsul RAM-da həddindən artıq yer tutulmasına, əlavə kopyalanma ilə CPU-nun yorulmasına və nəticə etibarilə performansı çox zəif olan bir əməliyyatın yerinə yetirilməsinə səbəb olur. Üstəlik funksional proqramlaşdırma dillərində (məsələn bizim nümunəmizdəki C dili kimi) Garbage Collector olmadığından RAM-da istifadəsi mümkün olmayan əvvəlki massivlərin yaddaşdan boşaldılması lazım gəlir( free() funksiyası ilə) ki, bu da əlavə bir əməliyyat deməkdir. Odur ki, praktik məqsədlər üçün Massivlər vasitəsilə Stack qurmaq tövsiyyə olunmur.

Yaddaş sahəsinin ölçüsünün yuxarı və aşağı sərhədləri təyin olunur. Əgər ayrılmış sahədə növbəti elementin struktura daxil edilməsi üçün boş yer ( slot ) yoxdursa, o zaman bu haqda istifadəçiyə strukturun “ dolub-daşması ” haqqında məlumat verilir.