11.2 Стек типіндегі құрылыммен жұмысты ұйымдаcтыру
Стек типіндегі құрылым әртүрлі есептеу үдерісінде кең қолданылады. Компьютер процессоры үзуді өңдеу барысында стекті қолданады. Алгоритмдердің көпшілігі алгоритмді алдыңғы қалпына «қайтаруды» орындау үшін стекттерді қолданады, мысалы, лабиринтті, графты немесе бұтақтарды жүріп өткен кезде. Көптеген көліктер туралы есептерді шешу алгоритмдерінде оңтайлы маршруттарды табу үшін стек пайдаланылады, т.б.
Әлбетте, «Алгоритмизация және бағдарламалау» пәнінде стек сияқты құрылымды қарастырмай өте алмаймыз, C# тілінде оған әдістер жиыны бар арнайы класс (Stack) бөлінген.
Стектермен жұмысты орындау барысында негізгі алгоритмдер: стекке элементті қосу алгоритмі, стектен элементті жою алгоритмі, стек мазмұнын қарау.
Стек типіндегі құрылымға қол жеткізу әдетте стек төбесі деп аталатын оның тек бір жақ шетінде ғана мүмкін.
Стек класы динамикалық коллекция – бір типтегі деректердің бірігуі түрінде бола алады. Стекті кеңейткен кезде («толтырылған» стекке элементті қосу барысында) стек сыйымдылығы динамикалық түрде екі есе үлкейеді.
Stack класында келесі үш конструктор анықталған:
Public Stack();
Public Stack(int capacity);
Public Stack(ICollection n);
Бірінші конструктор 10 элементтен тұратын «бос» стекті құрады. Екінші конструктор сыйымдылығы capacity болатын «бос» стекті құрады. Үшінші конструктор n элементті стекті құрады.
11.1-кестеде Stack класының негізгі әдістері ұсынылған.
11.1-кесте – Stack класының негізгі әдістері
Әдіс
|
Сипатама
|
public virtual bool Contains(object v)
|
True мәнін қайтарылады, егер v объектісі стекте болса, әйтпесе false мәні қайтарылады.
|
public virtual void Clear()
|
Стекті тазартады (Count қасиеті – стек элементтерінің саны нөлге теңестіріледі).
|
public virtual object Peek()
|
Стек төбесінің элементін қайтарады, бірақ оны жоймайды.
|
public virtual object Pop()
|
Стек төбесінің элементін қайтарады және оны жояды.
|
public virtual void Push(object v)
|
v элементін стекке қосады - стек төбесіне
|
Стек ішіндегісін көру үшін in операциясы жиі қолданылады, мысалы:
Console.Write("Стек ішіндегісі = ");
foreach (int i in vst)
Console.Write(i + " ");
Console.WriteLine();
Кодтың көрсетілген жолдары vst төбесінен және бүтін сандардан тұратын стекті қарап шығуға мүмкінді береді.
Стектермен жұмыс жасайтын алгоритмнің мысалы ретінде келесі есепті қарастырайық:
11.1-есебі. 5 бүтін саннан тұратын стек үшін санды қосу және шығару ықтималдығы кездейсоқ құрылады. Бұл орайда санды стекке қосу ықтималдығы 70% тең, ал стектен шығару 30% тең. Сандар кездейсоқ құрылады және минус 50 мен 50 аралығында болады.
Стекті толтыру барасында және стекке жаңа санды қосу кезінде, шығару ықтималдықтары қарама-қарсы мәндерге өзгереді. Бағдарлама жұмысының соңы санды «бос» стектен шығару мүмкіндігімен анықталады.
Бағдарламаның коды:
using System;
using System.Collections;
namespace ConsoleApplication1
{
class Program
{
static void vkl(Stack vst, int n)
{
vst.Push(n);
Console.Write("Stekke element zhazildi - {0}", n);
Console.Write("Stekte zhazildi = ");
foreach (int i in vst)
Console.Write(i + " ");
Console.WriteLine();
}
static void iskl(Stack vst)
{
if (vst == null) Console.WriteLine("Stek bos!");
else
{
int n = (int)vst.Pop();
Console.Write("Stekten element zhoildi {0}", n);
Console.Write("Stekte zhazildi = ");
foreach (int i in vst)
Console.Write(i + " ");
Console.WriteLine();
}
}
static void Main()
{
Stack vstek = new Stack();
int i, k, n;
Random rnd = new Random();
i = 0;
while (i < 5)
{
k = rnd.Next() % 101;
if (k <= 70)
{
i++;
n = rnd.Next() % 101 - 50;
vkl(vstek, n);
}
else
if (i > 0)
{
i--;
iskl(vstek);
}
}
Console.WriteLine("Stek tolik!");
while (i > 0)
{
k = rnd.Next() % 101;
if (k <= 30)
{
i++;
n = rnd.Next() % 101 - 50;
vkl(vstek, n);
}
else
if (i > 0)
{
i--;
iskl(vstek);
}
}
Console.WriteLine("Stek bos!");
Console.WriteLine("Enter pernesin basiniz");
Console.ReadLine();
}
}
}
Бағдарлама жұмысы:
Stekke element zhazildi - -6Stekte zhazildi = -6
Stekke element zhazildi - 12Stekte zhazildi = 12 -6
Stekke element zhazildi - 11Stekte zhazildi = 11 12 -6
Stekten element zhazildi 11Stekte zhazildi = 12 -6
Stekke element zhazildi - -8Stekte zhazildi = -8 12 -6
Stekke element zhazildi - -24Stekte zhazildi = -24 -8 12 -6
Stekke element zhazildi - 14Stekte zhazildi = 14 -24 -8 12 -6
Stek tolik!
Stekten element zhoildi 14Stekte zhazildi = -24 -8 12 -6
Stekten element zhoildi -24Stekte zhazildi = -8 12 -6
Stekten element zhoildi -8Stekte zhazildi = 12 -6
Stekten element zhoildi 12Stekte zhazildi = -6
Stekke element zhazildi - -27Stekte zhazildi = -27 -6
Stekke element zhazildi - -13Stekte zhazildi = -13 -27 -6
Stekten element zhoildi -13Stekte zhazildi = -27 -6
Stekten element zhoildi -27Stekte zhazildi = -6
Stekten element zhoildi -6Stekte zhazildi =
Stek bos!
Enter pernesin basiniz
Бағдарламада стекке элементті қосу және одан элементті шығару операцияларының әрқайсысына түсініктеме қосылған.
Достарыңызбен бөлісу: | 
