Misol uchun,
Stack stek1;
Stekda quyidagi amallar o’rinli:
-
Clear() - Stekni tozalash.
-
isEmpty() – Stekni bo’shlikka tekshirish
-
push(el) - stekka element kiritish.
-
pop() – Stekdan element o’chirish.
-
topEl() - stekni uchidagi elementni o’chirmasdan o’qib olish.
Ulardan foydalanish esa quyidagicha:
stek1.push(x) – x ni stekka tashlash;
Stekka element qo’shish va chiqarish amallari quyidagi 4.1 –
rasmda
ko’rsatib berilgan.
4.1 – rasm. Stekda bajarilgan amallar ketma – ketligi.
Unda bo’sh stekka 10 soni kiritilgan. Keyin stekka 5 soni kiritilgan, bu son
10 ni ustiga joylashadi, undan keyin chiqarish amali bajarilganda, stekdan 5 soni
o’chiriladi. Chunki u 10 sonining yuqorisida joylashgan edi va 5 soni stekdan
chiqariladi. Stekka 15 va 7 soni ketma - ket qo’yilgandan so’ng, eng yuqorida 7
soni bo’ladi. Natijada chiqarish operatsiyasi amalga oshirilganda 7 soni stekni
tark etadi. Chiqarish amalidan keyin stekda 10 soni 15 ning ostida qoladi.
Umuman olganda, stek ma’lumotlar saqlashda va ma’lumotlar to’plamidan
elementlar teskari tartibda chiqarib olinadigan holatlarda ko’p foydalaniladi.
Stekning
qo’llanilishlariga
misol qilib
dasturda ajratkichlarni
moslashtirishni olish mumkin. Bu juda ham muhim masala. Chunki, ajratkichlar
ixtiyoriy kompilyatorning qismi hisoblanadi. Agar ajratkichlar bir– biriga
moslashtirilmagan bo’lsa, hech bir dastur to’g’ri ishlamaydi.
C++ dasturlash tilida biz quyidagi ajratkichlarga egamiz:
oddiy qavslar
“(“va”)”, kvadrat qavslar “[“va”]”, figurali qavslar “[“va”]”, va izoh ajratkichlar
“/*” va “*/”. Quyida C++ dasturlash tilida ajratkichlar to’g’ri qo’llanilganligiga
misol keltirilgan.
a = b + (c - d) * (e - f);
g[10] = h[i[9]] + (j + k) * l;
while (m < (n[8] + o)) { p = 7; /* initialize p */ r = 6; }
Quyidagi misol moslashtirilmagan ajratkichlarga misol bo’la oladi:
a = b + (c - d) * (e - f));
g[10] = h[i[9]] + j + k) * l;
while (m < (n[8) + o]) { p = 7; /* initialize p */ r = 6; }
Konkret ajratgich o’z juftligidan boshqa ajratgichlar bilan ajratilishi
mumkin, ya’ni ajratkichlar ichma – ich qo’yilgan bo’lishi mumkin.
Shunday
qilib, ajratkich o’z juftligi bilan moslashganmi yoki yo’qligini, barcha ajratkichlar
juftliklari aniqlangandan keyin bilish mumkin.
Masalan, sikldan foydalanilganda boshlang’ich qavs o’z juftligiga ega
ekanligini barcha ichki qavslar juftliklari yopilgandan keyin aniqlash mumkin.
while (m < (n[8] + o))
Ajratkichlarni qiyoslash algoritmi quyidagicha:
- belgilar C++ dastur matnidan o’qiladi va u ochuvchi ajratkich bo’lsa, ular
stekka tashlanadi. Agar yopuvchi ajratkich bo’lsa, u ochuvchi ajrakich
bilan solishtiriladi va stekdan chiqariladi.
-
Agar ular mos tushsa, qayta ishlash davom etadi, mos tushmasa qayta
ishlash hatolik haqidagi habar bilan to’htatiladi.
Dastur ohiriga yetganda C++ dasturini qayta ishlash
muvoffaqiyatli tugatilgan
hisoblanadi va stek bo’sh bo’ladi. Ushbu algoritmni quyida psevdokodini
keltiramiz.
Ajratkichlarning moslashuvini tekshirish kodi.
read character ch
from file;
while
not end of file
if ch
is ‘(’, ‘[’, or ‘{’
push(ch);
else if ch
is ‘)’, ‘]’, or ‘}’
if ch
and popped off delimiter do not match
failure;
else if ch
is ‘/’
read the next character;
if
this character is ‘*’
skip all characters until “*/” is found and report an error
if the end of file is reached before “*/” is encountered;
else ch =
the character read in;
continue; //
go to the beginning of the loop;
// else
ignore other characters;
read next character ch
from file;
if
stack is empty
success;
else
failure;
4.2 rasmda yuqoridagi algoritmni quyidagi ifodani qayta ishlashga
qo’llanganda hosil bo’lgan qayta ishlash ko’rsatilgan
s=t[5]+u/(v*(w+y));
4.2 rasmdagi birinchi ustunda sikl ohiridan keyingi belgigacha bo’lgan stek
tarkibi ko’rsatilgan. Birinchi qator fayldagi va stekdagi boshlang’ich
holatni
ko’rsatilgan. Ch o’zgaruvchi s yozuv faylining birinchi simvoliga initsializatsiya
qilinadi, siklning birinchi iteratsiyasida simvol qabul qilinmaydi. Bu holat 4.2
rasmning ikkichi qatorida ko’rsatilgan. Undan keyin tenglik belgisi o’qiladi. U
ham qabul qilinmaydi, chunki u ajratkich emas. Birinchi ajratkich (kvadrat qavs )
5-qadamda o’qiladi va stekka birinchi element bo’lib joylashadi. Ifodaning barcha
elementlari o’qib chiqilgandan so’ng ajratkichlar birin – ketin stekka joylanadi,
va bu jarayon oxirgi nuqta vergulgacha davom etadi.
.
4.2-rasm.
Ajratkkichlar
moslashtirish
algoritmi
yordamida
s=t[5]+u/(v*(w+y)); ifodani tekshirish
Stekni qo’llanilishiga
boshqa misol qilib, juda katta sonlarni qo’shish
masalasini ko’rish mumkin. Bunday sonlar butun toifadagi o’zgaruvchilar uchun
mumkin bo’lgan chegaralardan chiqib ketadi. Shuning uchun ularni qo’shish
to’g’risida
gap
ham
bo’lishi
mumkin
emas.
Masalan,
18,274,364,583,929,273,748,459,595,684,373
va
8,129,498,165,026,350,236
sonlari berilgan. Ularni qo’shish muammosini sonlarni raqamlar qatori sifatida
tasvirlab, raqami bo’yicha ikkita stekka ketma – ket joylab qo’shish mumkin
bo’ladi. Bunda raqam sifatida sonlarni tartib xonalari (birlar , o’nlar, yuzlar…)
olinadi. Bu algoritmning psevdokodi quyidagicha:
Dostları ilə paylaş: