Yarim statik ma’lumotlar tuzilmalari

26 
Stekning tuzilmasi erkin foydalanish cheklangan ma’lumotlar tuzilmasi 
hisoblanadi, chunki faqat stekning cho’qqisida joylashgan elementdan erkin 
foydalanish mumkin bo’ladi. Bu element joriy element deb ataladi. Joriy 
elementning joyi to’g’risidagi axborot odatda stekning bosh uyasida joylashadigan 
stek cho’qqisining ko’rsatkichi (SCHK)da saqlanadi. 
Steklarni saqlash uchun ma’lumotlarni ham ketma-ket, ham bog’langan 
taqdim etishidan foydalanish mumkin. Ketma-ket taqdim etishdan foydalanganda 
stekning eng oxirgi o’lchamini bilish zarur. Ko’zda tutiladigan ushbu eng chekka 
o’lcham uchun moslab xotira zahiraga olinadi va uning ichida stek oshadi va 
qisqaradi. Blokning birinchi uyasi stek cho’qqisining ko’rsatkichini o’z ichiga 
oladi. Stek bo’sh bo’lganida ko’rsatkich o’zini-o’zi ko’rsatadi. Har bir yangi 
elementning kiritilganida cho’qqi ko’rsatkichi bir birlikka ko’payadi. 1.2-
chizmada xotira bloki va unda joylashgan boshlang’ich stek, shuningdek kiritilgan 
va chiqarib tashlangan elementli steklar tasvirlangan. Stekdan erkin foydalanishni 
shunday qilib tashkil etish mumkinki, bunda cho’qqi ko’rsatkichining qiymati stek 
mavjud bo’lgan hamma vaqt davomida o’zgarmas bo’lib qoladi. Bunday holatda 
erkin foydalanish har doim stek uchun moslab zahiraga olingan xotira blokining 
bitta uyasiga amalga oshiriladi. Shu uyaga cho’qqi ko’rsatkichi o’rnatiladi, unda 
stekning joriy (eng yuqori) elementi saqlanadi. Element kiritilganida yoki chiqarib 
1.2.1 chizma. Stekni ketma-ket taqdim etganda uning oshishi va kamayishi
Bo’sh 
makon 
A
n-1 
…
A
2 
A
1 
Cho’qqi 
ko’rsatkichi
Bo’sh 
makon
A
n-1
A
n-1 
…
A
2 
A
1 
Cho’qqi 
ko’rsatkichi
Bo’sh 
makon
A
n-1
A
n-1
A
n-1 
…
A
2 
A
1 
Cho’qqi 
ko’rsatkichi

27 
tashlanganida stekning barcha elementlari xotira blokining ichida mos ravishda 
pastga yoki yuqoriga siljiydi. Bunday holatda kiritish operatsiyasini «itarib 
kirgizish», chiqarib tashlash operatsiyasini esa - «itarib chiqarish» 
deyiladi.Shuning uchun tuzilmaning buzilishi uning xususiyatlari yo’qolishiga va 
oqibatda obyektning nomuvofiq ta’riflanishiga olib keladi. 
Ketma-ket taqdim etishning kamchiligi shundan iboratki, stekning to’lib 
ketishi xavfi hamisha bo’ladi; aks holda zahiraga olingan xotiraning bir qismi 
ishlatilmay qoladi. Ma’lumotlarni bog’langan taqdim etishdan foydalanganda stek 
uchun moslab xotirani oldindan zahiraga olishning zarurati bo’lmaydi. Stekning 
barcha elementlari xotira bo’yicha yoyib tashlanadi va o’zaro ko’rsatkichlar bilan 
bog’lanadi. SCHK stekning eng yuqoridagi elementi joylashgan uyaga ko’rsatadi. 
Elementlar kiritilganida yoki chiqarib tashlanganida cho’qqi ko’rsatkichining 
qiymati o’zgaradi. Yangidan kiritilayotgan element xotiraning ixtiyoriy bo’sh 
uyasiga joylashtiriladi va u mos ravishda bog’langan ro’yxat ko’rsatkichlarini 
o’zgartirish yo’li bilan stekka qo’shiladi. Ma’lumotlarni bog’langan taqdim etishda 
stek cheksiz oshishi mumkin. Ma’lumotlar mazmuniy mohiyatini baholashsiz 
kiritish va chiqarib tashlash operatsiyalarini tezlik bilan bajarish talab etilgan 
SChK 
A
n-1 
….. 
A1 
A
n+1 
A
n 
….. 
A1 
A
n 
A
n-1 
….. 
A1 
SChK 
A
n+1 
SChK 
Bo’sh 
makon 
Bo’sh 
makon 
Bo’sh 
makon 
1.2.2-chizma O’zgarmas ko’rsatkich bilan stekning oshishi va kamayish.

28 
vaziyatlarda stekning tuzilmasi juda qulay keladi. Asosiy ro’yxatdan o’chirilgan 
ixtiyoriy uya bo’sh xotira stekining cho’qqisiga qo’shiladi. Bo’sh xotira stekiga 
kiritilgan so’nggi uya asosiy ro’yxatning yangi yozuvini joylashtirish uchun 
birinchi bo’lib ishlatiladi. Bo’shagan uyalarni bo’sh xotira stekiga kiritilishini 
boshqaradigan algoritm ko’pincha «axlat yig’uvchi» deb ataladi. 
Stekli tuzilmalar ichiga qo’yilgan kichik dasturlar va ko’p pog’onali 
uzilishlarni amalga oshirishda translyatorlarda, shuningdek algoritmlari rekursiv 
usul bilan eng yaxshi ta’riflanadigan vazifalarni echishda keng qo’llaniladi. 
Navbat bu o’zgaruvchan o’lchamdagi chiziqli tuzilmadir. Elementlarni 
navbatdan chiqarib tashlashga bir tomondan - navbatning boshidan ruxsat beriladi. 
Elementlarni kiritish faqat teskari tomonga - navbatning oxiriga bo’lishi mumkin. 
Bunday tuzilmadagi ma’lumotlar ular kelib tushishiga qarab «birinchi keldi, 
birinchi ketdi» tamoyili bo’yicha qayta ishlanadi. Adabiyotda navbat tuzilmasini 
FIFO (inglizcha First In, First Out) tipidagi tuzilma deyiladi. Svetoforning 
ochilishini kutayotgan avtomobillar navbati an’anviy misol hisoblanadi. 
Svetoforga birinchi bo’lib kelgan avtomobil chorrahadan birinchi bo’lib o’tib 
ketadi, ya’ni navbatdan chiqariladi. Oxirida kelgan va navbatning oxirida o’tib 
ketishni kutayotgan avtomobilb chorrahadan oxirgi bo’lib o’tadi. 
Navbat elementlaridan erkin foydalanish boshlanish va tugash ko’rsatkichi 
bo’yicha amalga oshiriladi. Boshlanish ko’rsatkichi birinchi bo’lib chiqarib 
tashlanadigan yoki o’qiladigan navbat elementini ko’rsatadi. Tugash ko’rsatkichi 
navbatdagi so’nggi yozuvdan keyin keladigan xotiraning bo’sh uyasiga o’rnatiladi.
Yangi kelgan yozuv, ya’ni navbatning yangi elementi aynan shu uyaga 
joylashadi. Navbat tuzilmasini amalga oshirish uchun KOMPYUTER xotirasida 
ma’lumotlarni ham ketma-ket, ham bog’langan taqdim etishdan foydalaniladi. 

29 
1.2.3-chizma. Navbat 
Navbatga ketma-ket taqdim etishda stekdagi kabi xotira bloki z ahiraga 
olinadi, uning ichida navbat oshishi va kamayishi mumkin. Har bir yangi element 
kiritilishi bilan tugash ko’rsatkichi birlikka o’zgaradi. Yangi elementlarni kiritish 
natijasida navbat tugashi ko’rsatkichi zahiraga olingan xotira blokining oxiriga 
etsa, u blokning boshiga ko’chiriladi. Agar tugash ko’rsatkichi boshlanish 
ko’rsatkichiga etib olsa, bu xotira bloki to’lganligini anglatadi. 
Elementni chiqarib tashlashda boshlanish ko’rsatkichi birlikka o’zgaradi. 
Agar boshlanish ko’rsatkichi tugash ko’rsatkichi bilan mos tushsa, navbat bo’sh 
bo’ladi. Ma’lumotlarni ketma-ket taqdim etishda zahiraga olingan xotira bloki 
ichidagi navbatni joylashtirish sxemasi 1.2.3-chizmada tasvirlangan. Shu yerning 
o’zida navbat elementlarini kiritish va chiqarib tashlashda ko’rsatkichlar qanday 

30 
o’zgarishi ham ko’rsatilgan. 
Navbatni bog’langan taqdim etishda xotirani oldindan zahiraga olish talab 
etilmaydi. Navbatni shakllantiruvchi yozuvlar ixtiyoriy bo’sh xotira uyalarida 
joylashadi va o’zaro ko’rsatkichlar bilan bog’lanadi. Bunday navbat cheksiz 
oshishi mumkin. Elementlarni kiritish va chiqarib tashlashda faqat boshlanish va 
tugash ko’rsatkichlarining qiymati va aloqa ko’rsatkichlarining qiymati (AS) 
o’zgaradi, xolos. 
Navbat tuzilmasi ma’lumotlarni qayta ishlashning turli vazifalarini echishda 
ishlatiladi. Masalan, vaqtni taqsimlash bilan hisoblash tizimini modellash navbat 
tuzilmasi ishlatiladigan an’anviy vazifalardan biri hisoblanadi. Bunday tizimda 
ko’pchilik foydalanuvchilar bir vaqtning o’zida bitta asosiy xotiradan foydalanib 
yagona 
markaziy 
protsessor 
bilan 
ishlaydi. 
Bajarilishni 
kutayotgan 
foydalanuvchilarning dasturlari navbatni tashkil etadi. Navbatni tashkil etish va 
unga xizmat ko’rsatishning ishlab chiqilgan tamoyili ko’p jihatdan bunday tizim 
ishlashining samaradorligini belgilab beradi.
Ko’rsatkichlar ishtirok etadigan dasturlarga misollar. 
Stekka element qo’shish, olib tashlash 
procedure udals; begin 
top:=top
^
.next 
end. 
Stek elementlarini qo’shish 
procedure rasps; 
{elementlarni teskari tartiblab chiqarish} begin
kop:=top; 
while kop 
<>NIL do 
begin 
writeln (kop
^
.INF); 
kop:=kop
^
.next 
end; 

31 
Stekni ishlatganda quyidagi xolatlar yuzaga kelishi mumkin: 
1. 
stekning tulib ketishi, ya’ni stek xotirasida joy kolmaslik. 
2. 
Tulmaslik xolati stekdan u bush bulganda ukishga xarakat 
kilish. Navbat-ma’lumotlarning shunday tuzilmasiki, uning bir tomonida 
element qo’shib borilsa, ikkinchi tomonidan olib tashlanadi. 
Bunday tuzilmani tashkil kilish uchun LEFT va RIGHTo’zgaruvchilari 
ishlatiladi. 
Navbatga 
element 
kushilayotganda, 
elementlar 
RIGHT 
o’zgaruvchisining qiymatiga mos xotiraga joylashadi. SHunday kilib, RIGHT 
xotiraning bush joyini kursatadi. Navbatdan elementlarni tanlash navbatning 
keyingi elementini kursatuvchi qiymat orqali amalga oshadi. Agar LEFT qiymati 
RIGHT qiymatiga teng bo’lsa, u xolda navbat bush xisoblanadi. 
Navbat ustida xam quyidagi amallarni bajarish mumkin: 
navbatni tashkil kilish; 
navbatga kushish; 
navbatdan olib tashlash; 
navbatga elementlarini kurish. 
Shunday qilib, navbat aylana shaklidagi ro’yxatdan iboratdir. 

Download 1.28 Mb.