Fan: ma’lumotlar tuzilmasi va algoritmlar mustaqil ish mavzu: Yarim statik ma’lumotlar tuzilmalari

O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA MAXSUS TA’LIM VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Guruh:061-19

Topshirdi:Abdusattarova Gulchehra
Qabul qildi:Dilfuza G’anixodjayeva

Fan: MA’LUMOTLAR TUZILMASI VA ALGORITMLAR

MUSTAQIL ISH

Mavzu: Yarim statik ma’lumotlar tuzilmalari


Yarim statik ma’lumotlar tuzilmalari. 

Stek - massiv tuzilmasidan farqli ravishda, elementlarni kiritish yoki 
chiqarib tashlashga imkon beradigan o’zgaruvchan o’lchamning chiziqli 
tuzilmasidir, ya’ni stekda ma’lumotlar hajmi dasturning bajarilishi vaqtida uyg’un 
ravishda oshishi va kamayishi mumkin. 
Stekli tuzilmaning xususiyati shundan iboratki, elementlardan erkin 
foydalanish, elementlarni kiritish va chiqarib tashlash faqat tuzilmaning bir 
tomonidan - stek cho’qqisidan mumkin bo’ladi. SHuning uchun stekka oxirida 
kiritilgan element birinchi bo’lib o’qiladi yoki tanlanadi. Bunday tuzilmada 
axborot «oxirida keldi, birinchi ketdi» tamoyili bo’yicha qayta ishlanadi. Stekning 
tuzilmasini ba’zan LIFO (inglizcha Last In, First Out) tipidagi tuzilma deyiladi, bu 
qachonki faqat yuqoridagi likobchani olish mumkin bo’lgan likobchalar to’plami 
misolida yaxshi tushuniladi. Avval yuqoridagi likobchani, so’ngra keyingisini 
olish mumkin. Likobchalar to’plamning yuqori qismiga bittadan qo’shiladi. 
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.