DASTURIY TAMINOT TO’PLAMI
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.
Dostları ilə paylaş: |