O’zbekiston Respublikasi Samarqand Davlat Universiteti Raqamli texnologiyalar fakulteti Amaliy

DASTURIY TAMINOT TO’PLAMI

1. Amalga oshirish 

Stackni massiv yoki bog'langan ro'yxat orqali osongina amalga oshirish mumkin . Ma'lumotlar strukturasini stek sifatida belgilaydigan narsa, har qanday holatda ham, amalga oshirish emas, balki interfeysdir: foydalanuvchiga faqat bir nechta yordamchi operatsiyalar bilan massiv yoki bog'langan ro'yxatga elementlarni ochish yoki surish mumkin. Quyida pseudocode dan foydalangan holda ikkala dastur ham ko'rsatiladi .

Massiv 

Massivdan (chegaralangan) stekni amalga oshirish uchun quyidagi tarzda foydalanish mumkin. Birinchi element, odatda nol ofsetda , pastki qism bo'lib, natijada array[0]stekga surilgan birinchi element bo'ladi va oxirgi element ochiladi. Dastur stekning o'lchamini (uzunligini) kuzatib borishi kerak, bu o'zgaruvchan tepadan foydalanib , shu paytgacha surilgan elementlarning sonini yozadi, shuning uchun massivdagi keyingi element kiritilishi kerak bo'lgan joyga ishora qiladi (nol bo'lsa). asoslangan indeks konventsiyasi). Shunday qilib, stekning o'zi uch elementli tuzilma sifatida samarali amalga oshirilishi mumkin:

struktura stek:

maxsize: butun son

yuqori: butun son

ob'ektlar: element qatori

protsedurani ishga tushirish (stk: stek, o'lcham: tamsayı):stk.items ← o'lchamdagi elementlarning

yangi qatori , dastlab bo'sh

stk.maxsize ← hajmi

stk.top ← 0

Surish operatsiyasi elementni Iqo'shadi va to'lib ketishini tekshirgandan so'ng yuqori indeksni oshiradi:

protsedurani surish (stk: stek, x: element):

agar stk.top = stk.maxsize:

to'ldirish xatosi haqida xabar bering

boshqa :

stk.items[stk.top] ← x

stk.top ← stk.top + 1

Xuddi shunday, pop past oqim borligini tekshirgandan so'ng yuqori indeksni pasaytiradi va avval yuqori bo'lgan elementni qaytaradi:

protsedura pop (stk: stack):

agar stk.top = 0 bo'lsa:

past oqim xatosi haqida xabar bering

boshqa :

stk.top ← stk.top − 1

r ← stk.items[stk.top]

qaytish r

Dinamik massivdan foydalanib , kerakli darajada o'sishi yoki qisqarishi mumkin bo'lgan stekni amalga oshirish mumkin. Stakning o'lchami shunchaki dinamik massivning o'lchamidir, bu stekning juda samarali amalga oshirilishidir, chunki dinamik massiv oxiridan elementlarni qo'shish yoki olib tashlash amortizatsiya qilingan O(1) vaqtni talab qiladi.