1. Стеклер

LIFO, яғный нәўбеттиң ақырғы болып кирган элементине биринши болып хызмет көрсетиледи. Бул ең көп ислетилетуғын мағлыўматлар структураларынан бири болып, ҳәр түрли мәселелерди шешиўде бир қанша қолай ҳәм нәтийжели есапланады.

Хызмет көрсетиўди келтирилген тәртибине көре, стекте тек ғана бир позицияға мүрәжәт етиў мүмкин. Бул позиция стектиң ушы делинип онда стекке ўақыт бойынша ең ақырғы келип түскен элемент нәзерде тутылады. Биз стекке жаңа элемент киритсек, бул элемент алдыңғы стек ушында турған элемент үстине жайластырылады ҳәмде стектиң ушында жайласып қалады. Элементти тек ғана стек ушынан таңлаў мүмкин; бунда таңланған элемент стектен шығарып тасланады ҳәм стек ушы болса шығарып тасланған элементтен бир адым алдын келип түскен элемент шөлкемлестирилип қалады. (бундай структураға мағлыўматларға шекленген мүрәжәт структурасы делинеди).

Стекти графикалық көринисинде төмендегише көрсетиў мүмкин:

Биринши элемент стек төменине киритиледи.

Стек үстинде әмелге асырылатуғын әмеллер:

1. PUSH( s , i ) – стекке элемент киритиў, бул жерде s – стек аты, i - стекке киритилетуғын элемент;

2. POP ( s ) – стектен элементти танлаў. Элемент таңланып атырғанда өзи ийелеп турған жумысшы ядқа жайластырылады;

3. EMPTY ( s ) – стектиң бос яки бос емеслегин тексериў (true - бос, false – бос емес);

4. STACKTOP ( s ) – стек жоқарғы элементин өширместен оқыў.

Стек жаратыў программасы фрагменти (зәрүр процедурлар)

Program STACK;

const

max_st=50;

const

max_st=50;

var

st,st2: array[1..max_st] of integer;

n:integer;

function empty:boolean; {Стекте элемент барлығын тексериў}

begin

empty:=n=0

end;

procedure push(a:char); {стекке элементти жайласытырыў}

begin

inc(n);

st[n]:=a;

end;

procedure pop(var a:char); {стектен элементти ажыратып алыў}

begin

a:=st[n];

dec(n);

end;

function full:boolean; {толықлыққа тексериў}

begin

Full:=n=max_st

end;

procedure stacktop(var a:char); {жоқары элементти анықлаў}

begin

a:=st[n];

end;

begin {тийкарғы программа}

.

.

end.

2. Нәўбет

Программаластырыўда сондай мағлыўматлар структурасы бар, ол нәўбет делинеди. Бундай мағлыўматлар структурасы реал нәўбетти моделлестириўде үлкен әҳмийетке ийе. Бунда хызмет көрсетиўге келип түскен талап, оның орынланыўы, яғный хызмет көрсетиў тәртибин анықлаўда зәрүр болады. Күнделик өмиримизде барлығымызға белгили болған нәўбет түри, программаластырыўда FIFO (First input-First output, яғный биринши келген – биринши кетеди) деп аталады. Төменде 4 элементтен ибарат нәўбет келтирилген.

Бул жерден көринип турыпты, стектен парқлы түрде хызмет көрсетилиў биринши келген элементке биринши болып хызмет көрсетиледи. Стектен және бир парқы, бунда нәўбеттиң ҳәр еки тәрепи ашық болады, яғный бир тәрептен келип екинши тәрептен шығып кетеди.

Демек, нәўбеттен элементти алыў дизим басынан, жазыў болса ақырынан әмелге асырылады.

ЭЕМ ядында реал нәўбет эементлери саны шекли болған бир өлшемли массив көринисинде жаратылады. Әлбетте, бунда нәўбет элементиң түрин көрсетиў ҳәм нәўбет пенен ислеўди көрсетиўши өзгериўши зәрүр болады.

Нәўбет физикалық басқышта яд тараўын дизим избе-излиги бойынша толығы менен ийелейди.

Нәўбет үстинде әмелге асырылатуғын әмеллер:

Нәўбет ушын 3 әпиўайы әмел анықланған.

1. Нәўбетке жаңа элемент жайластырыў: insert (q,x), бул жерде q-нәўбет, x – элемент.

2. Нәўбет басынан элементти өшириў: remove(q)

3. Нәўбеттиң бос яки бос емеслигин анықлаў: empty (q)

Буннан тысқары, нәўбет бир өлшемли массив көринисинде аңлатылғанлығы ушын массивти толық яки толық емеслигин гүзетип турыў лазым болады. Сол мақсетте, full(q) әмели киритиледи.

Улыўма алғанда, insert әмелин ҳәр дайым орынлаў мүмкин. Себеби, нәўбетти шөлкемлестириўши элементлер санына шеклениўлер қойылмаған. Remove әмели болса тек ғана нәўбет бос болмағанда ғана ислейди. Empty әмели болса ҳәр дайым орынлы.

Паскал тилинде нәўбетти бир өлшемли массив көринисинде әмелге асырыўға мысал:

const

MaxQ = ...

type

E = ...

Navbat = Array [1..MaxQ] of E;

var

Q: Navbat;

F, R: Integer;

{F көрсеткиш нәўбет басын көрсетеди. R болса нәўбет ақырын. Егер нәўбет бос болса, ол жағдайда F = 1 ҳәм R = 0 болады. (яғный R < F – нәўбеттиң бослық шәрти).}

Procedure Insert(I: Integer; var Q: Navbat);

begin

Inc(R);

Q[R]:=I;

end;

Function Empty(Q: Navbat): Boolean;

begin

If R < F then Empty:=True Else Empty:=False;

end;

Procedure Remove(var I: Integer; Q: Navbat);

begin

If Not Empty(Q) then

begin

I:=Q[F];

Inc(F);

end;

end;

Стандарт процедуралар жәрдеминде нәўбет пенен ислеўге мысал.

MaxQ = 5

A, B ҳәм C элементлерди нәўбетке қояйық.

Insert(q, A);

Insert(q, B);

Insert(q, C);

A ҳәм B элементлерди нәўбеттен шығарамыз.

Remove(q);

Remove(q);

Тилекке қарсы, нәўбетти бундай көринисте аңлатыў, биймәни, логикасыз жағдайға алып келиўи мүмкин. Себеби, бундай аңлатылғанда, нәўбет бос болсын, деп ойлайық, бирақ оған жаңа элемент қойып болмайды (элементлерди қосыў ҳәм шығарыў әмеллерин орынлап усы жағдайға алып келиң). Көринип турыпты, нәўбетти массив көринисте аңлатыў номақбул (неприемлемо) екен.

Жүзеге келген машқаланы ретлестириўдиң шешимлеринен бири remove әмелин төмендегише модификация қылыў болып есапланады. Нәўбеттеги элемент өширилгенде, нәўбеттиң барлық элементлери массив басына сүриледи (жайластырылады). Бундай жағдайда remove (q) әмелин төмендегише әмелге асырыў мүмкин.

X = q[1]

For I =1 to R-1

q[I] =q[I+1]

next I

R =R-1

Бунда F өзгериўшиге мүтәжлик қалмайды, себеби, массивтиң биринши элементи ҳәр дайым нәўбет басы болып есапланады. Егер нәўбет бос болса, ол жағдайда R диң мәниси ноль болады.

Бирақ бул усыл бир қанша нәтийжесиз. Себеби, нәўбеттен элементини өшириў ҳәр дайым нәўбеттиң қалған элементлерин жылжытыўды талап қылады. Егер нәўбет элементлери саны қанша үлкен болса, оны әмелге асырыў бираз нәтийжесиз болады. Буннан тысқары, элементти нәўбеттен өшириў әмели, логикалық жақтан, тек ғана бир элементти, яғный нәўбет басында жайласқан элементти басқарыўдан ибарат болады. Бундай усылдан, тек ғана өшириў жумысын орынлап, басқа қосымша жумысларды әмелге асырмағанда пайдаланса болады. Ойлайық, нәўбет басындағы элементти емес, бәлким басқа элементти өширмекшимиз, ол жағдайда жоқарыдағы усылдан пайдаланып болмайды.

Нәўбетти аңлатыўға және басқаша жандасыў, бул массивти сызықлы избе-излик көринисинде емес, бәлким басы ҳәм ақырына ийе болған сызықлы емес жабық ҳалқа көринисте аңлатыў. Буннан келип шығады, нәўбеттиң биринши элементи, ақырғы элементинен кейинрек келеди. Бул болса егер соңғы элемент бәнт болғанда да биринши элемент бос болса, оның орнына ақырғы элементтен кейин жайластырады.

Ҳалқа тәризли нәўбетти пайда етиў.

Мысал көремиз. Ойлайық, нәўбет 5 элементли массивте 3 элементке ийе болсын: 3-ши, 4-ши ҳәм 5-ши орынларда. Усы жағдай жоқарыдағы сызылмада келтирилген. Массив толған болмасада, нәўбеттиң соңғы элементи бәнт. Енди, егер нәўбетке G элемент жайластырмақшы болса, ол жағдайда бул элемент массивтиң биринши орнына (позициясына) жазылады. Нәўбеттиң биринши элементи бул жерде Q(3), оннан кейин Q (4), Q(5) ҳәм Q(l) элементлер келеди.

Тилекке қарсы, нәўбеттиң бундай аңлатылыўында, оның бослығын анықлаў жетерли дәрежеде қыйын болады. Нәўбеттиң бослығын тексериў ушын енди R<F шәрти басқа жарасмайды.

Усы машқаланы ретлестириўдиң шешимлеринен бири “келисиў”ди киритиў, бунда F тың мәниси нәўбеттиң биринши элементинен кейин келиўши массив индекси болады, лекин бул индекс ең биринши элементтиң индекси емес. Бундай жағдайда, R нәўбеттиң ең соңғы элемент индексин билдиргенлиги себепли, F = R шәрти нәўбеттиң бослығын аңлатады.

Еслетип өтемиз, нәўбет пенен ислеўде F ҳәм R ге 0 ҳәм 1 емес, бәлким нәўбеттиң ақырғы элемент индекси мәнислери белгиленеди, себеби, нәўбетти бундай көринисте аңлатқанымызда, массивтиң соңғы элементи тез арада биринши элементиниң артында болады. Себеби, R = F болғаны ушын нәўбет басында бос болады.

Ҳалқа тәризли нәўбеттеги тийкарғы әмеллер:

1. Нәўбетке элемент қосыў.

Insert(q,x)

2. Нәўбеттен элементти шығарып таслаў.

Remove(q)

3. Нәўбеттиң бослығын тексериў.

Empty(q)

empty (q) әмелин төмендегише жазыў мүмкин:

if F = R

then empty = true

else empty = false

endif

return

remove (q) әмелин төмендегише жазыў мүмкин:

empty (q)

if empty = true

then print «бос нәўбеттен таңлаў»

stop

endif

if F =maxQ

then F =1

else F = F+1

endif

x = q(F)

return

Соны есте тутыў лазым, F тиң мәниси элементти ажыратып алынғанша модификация қылыныўы лазым.