Паскал тилида навбатни бир ўлчамли массив кўринишда амалга
оширишга мисол:
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 нинг қиймати ноль бўлади.
Бироқ бу усул анча самарасиз. Чунки, навбатдан элементини ўчириш
доимо навбатнинг қолган элементларини силжтишни талаб қилади. Агар
навбат элементлари сони қанча катта бўлса, уни амалга ошириш анча
самарасиз бўлади. Бундан ташқари, элементни навбатдан ўчириш амали,
мантиқан олганда, фақатгина битта элементни бошқаришдан иборат бўлади,
яъни навбат бошида жойлашган элементни. Бундай усулдан, фақатгина
ўчириш ишини бажариб, бошқа қўшимча ишларни амалга оширмаганда
фойдаланса бўлади халос. Фараз қилайлик, навбат бошидаги элементни эмас,
―Маълумотлар тузилмаси ва алгоритмлар‖ фанидан маърузалар матни.
муаллиф: Б.Б.Акбаралиев
балки бошқа элементни ўчирмоқчимиз, у ҳолда юқоридаги усулдан
фойдалниб бўлмайди.
Навбатни ифодалашга яна бошқача ѐндашув, бу массивни чизиқли
кетма-кетлик кўринишида эмас, балки боши ва охирига эга бўлган чизиқсиз
ѐпиқ ҳалқа кўринишда ифодалашдир. Бундан келиб чиқадики, навбатнинг
биринчи элементи, охирги элементидан кейиноқ келади. Бу эса агар сўнги
элемент банд бўлган тақдирда ҳам биринчи элемент бўш бўлса, унинг ўрнига
оҳирги элементдан кейин жойлашади.
Do'stlaringiz bilan baham: |