O’zbekiston Respublikasi Samarqand Davlat Universiteti Raqamli texnologiyalar fakulteti Amaliy

import java.util.Stack ;
class StackDemo {

public static void main ( String [] args ) {

Stack < String > stack = new Stack < String > ();

stack . surish ( "A" ); // stekga "A" ni

qo'ying . surish ( "B" ); // stekga "B" ni

qo'ying . surish ( "C" ); // stekga "C" ni

kiriting .surish ( "D" ); // stek tizimiga "D" ni kiriting

. tashqariga . println ( stack . peek ()); // stekning yuqori qismini ("D") chop etadi . pop (); // yuqori ("D") stekni olib tashlash . pop (); // keyingi tepani olib tashlash ("C") } }

3. Stackning asosiy arxitekturasi.

Ko'p darajadagi protsedura chaqiruvlari uchun mahalliy ma'lumotlar va qo'ng'iroqlar ma'lumotlarini saqlaydigan odatiy stek. Bu stack o'zining kelib chiqishidan pastga qarab o'sadi. Stack ko'rsatkichi stekdagi joriy eng yuqori ma'lumotlarga ishora qiladi . Surish operatsiyasi ko'rsatkichni pasaytiradi va ma'lumotlarni stekga ko'chiradi; pop operatsiyasi ma'lumotlarni stekdan nusxa ko'chiradi va keyin ko'rsatgichni oshiradi. Dasturda chaqirilgan har bir protsedura protsedurani qaytarish ma'lumotlarini (sariq rangda) va mahalliy ma'lumotlarni (boshqa ranglarda) stekga surish orqali saqlaydi. Ushbu turdagi stekni amalga oshirish juda keng tarqalgan, ammo bufer to'lib-toshgan hujumlarga nisbatan zaifdir (matnga qarang).

Odatiy stek - bu sobit kelib chiqishi va o'zgaruvchan o'lchamli kompyuter xotirasi maydoni. Dastlab stekning o'lchami nolga teng. Odatda apparat registri ko'rinishidagi stek ko'rsatkichi stekdagi eng so'nggi havola qilingan joyni ko'rsatadi; stekning o'lchami nolga teng bo'lsa, stek ko'rsatkichi stekning kelib chiqishiga ishora qiladi.

Barcha steklarga qo'llaniladigan ikkita operatsiya:

• 
  surish operatsiyasi, bunda ma'lumotlar elementi stek ko'rsatkichi ko'rsatgan joyga joylashtiriladi va stek ko'rsatkichidagi manzil ma'lumotlar elementining o'lchamiga qarab sozlanadi;
  
• 
  pop yoki tortish operatsiyasi: stek ko'rsatgichi ko'rsatgan joriy joylashuvdagi ma'lumotlar elementi olib tashlanadi va stek ko'rsatkichi ma'lumotlar elementining o'lchamiga qarab o'rnatiladi .
  

Stack operatsiyalarining asosiy printsipida ko'plab o'zgarishlar mavjud. Har bir stek o'zi boshlanadigan xotirada ma'lum bir joyga ega. Ma'lumotlar elementlari stekga qo'shilganda, stek ko'rsatkichi boshlang'ichdan uzoqroqqa kengayadigan stekning joriy hajmini ko'rsatish uchun almashtiriladi.

Stack ko'rsatkichlari stekning kelib chiqishini yoki manzilning cheklangan diapazonini ko'rsatishi mumkin (stekning o'sish yo'nalishiga qarab); biroq, stek ko'rsatkichi stekning kelib chiqishini kesib o'ta olmaydi. Boshqacha qilib aytganda, agar stekning kelib chiqishi 1000-manzilda bo'lsa va stek pastga qarab o'sadigan bo'lsa (999, 998 va hokazo manzillar tomon), stek ko'rsatkichi hech qachon 1000 dan (1001, 1002 va hokazo) oshib ketmasligi kerak. Agar stekdagi pop operatsiyasi stek ko'rsatkichini stekning boshlang'ich joyidan o'tishiga sabab bo'lsa, stekning kam oqimi sodir bo'ladi. Agar surish operatsiyasi stek ko'rsatkichini stekning maksimal chegarasidan tashqariga ko'payishiga yoki kamayishiga olib kelsa, stek to'lib ketishi sodir bo'ladi.

Steklarga ko'p tayanadigan ba'zi muhitlar qo'shimcha operatsiyalarni ta'minlashi mumkin, masalan:

• 
  Dublikat : yuqori element ochiladi va keyin yana (ikki marta) suriladi, shunda avvalgi yuqori elementning qo'shimcha nusxasi endi tepada, asli esa uning ostida joylashgan.
  
• 
  Ko'zdan kechirish : eng yuqori element tekshiriladi (yoki qaytariladi), lekin stek ko'rsatkichi va stek hajmi o'zgarmaydi (ya'ni element stekda qoladi). Bu ko'plab maqolalarda yuqori operatsiya deb ham ataladi .
  
• 
  Almashtirish yoki almashish : stekdagi ikkita eng yuqori element almashish joylari.
  
• 
  Rotate (yoki Roll) : n ta eng yuqori element aylanma tarzda stekga ko'chiriladi. Misol uchun, agar n =3 bo'lsa, stekdagi 1, 2 va 3-bandlar mos ravishda stekning 2, 3 va 1 pozitsiyalariga ko'chiriladi. Ushbu operatsiyaning ko'plab variantlari mumkin, eng keng tarqalgani chapga aylantirish va o'ngga aylantirish deb ataladi.
  

Ko'pincha steklar pastdan yuqoriga ko'tariladi (masalan, haqiqiy steklar). Ular, shuningdek, chapdan o'ngga o'sib borayotganini ko'rish mumkin, shunda "eng yuqori" "eng o'ngga" aylanadi yoki hatto yuqoridan pastgacha o'sadi. Muhim xususiyat shundaki, stackning pastki qismi qattiq holatda. Ushbu bo'limdagi rasm yuqoridan pastgacha o'sish vizualizatsiyasiga misoldir: tepa (28) "pastki" stekdir, chunki "yuqori" stek (9) elementlarning surilishi yoki ko'tarilishi joyidir.

O'ngga aylantirish birinchi elementni uchinchi holatga, ikkinchisini birinchisiga va uchinchisini ikkinchisiga o'tkazadi . Mana bu jarayonning ikkita ekvivalent vizualizatsiyasi:

olma banan

banan ===o'ngga aylantirish ==> bodring

bodring olma

bodring olma

banan ===chapga aylantirish==> bodring

olma banan

Odatda stek kompyuterlarda xotira kataklari bloki bilan ifodalanadi, “pastki” belgilangan joyda, stek ko‘rsatkichi esa stekdagi joriy “yuqori” yacheyka manzilini ushlab turadi. Yuqori va pastki terminologiyalar stek aslida past xotira manzillariga yoki yuqoriroq xotira manzillariga qarab o'sishidan qat'iy nazar ishlatiladi.

Elementni stekga surish stek ko‘rsatkichini elementning o‘lchami bo‘yicha sozlaydi (stek xotirada o‘sish yo‘nalishiga qarab kamaytiriladi yoki ko‘paytiriladi), uni keyingi katakchaga yo‘naltiradi va yangi yuqori elementdan nusxa ko‘chiradi. stack maydoni. Yana aniq amalga oshirilishiga qarab, surish operatsiyasi oxirida stek ko'rsatkichi stekdagi keyingi foydalanilmagan joyni ko'rsatishi yoki stekdagi eng yuqori elementni ko'rsatishi mumkin. Agar stek joriy eng yuqori elementga ishora qilsa, yangi element stekga surilishidan oldin stek ko'rsatkichi yangilanadi; agar u stekdagi keyingi mavjud joyni ko'rsatsa, u yangi element stekga surilgandan so'ng yangilanadi.

Stackni ochish shunchaki surishning teskarisi. Stackning eng yuqori elementi olib tashlanadi va stek ko'rsatkichi surish operatsiyasida ishlatilganiga teskari tartibda yangilanadi.

4. 
   Ortga qaytish va havfsizlik