I. Kirish Ma’lumotlar bazasi haqida tushuncha. Ma’lumotlar tuzilmasi haqida tushunchalar. Statik turdagi ma’lumotlar tuzilmasi

Паскал тилида навбатни бир ўлчамли массив кўринишда амалга оширишга мисол:
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 нинг қиймати ноль бўлади.

Бироқ бу усул анча самарасиз. Чунки, навбатдан элементини ўчириш доимо навбатнинг қолган элементларини силжтишни талаб қилади. Агар навбат элементлари сони қанча катта бўлса, уни амалга ошириш анча самарасиз бўлади. Бундан ташқари, элементни навбатдан ўчириш амали, мантиқан олганда, фақатгина битта элементни бошқаришдан иборат бўлади, яъни навбат бошида жойлашган элементни. Бундай усулдан, фақатгина ўчириш ишини бажариб, бошқа қўшимча ишларни амалга оширмаганда фойдаланса бўлади халос. Фараз қилайлик, навбат бошидаги элементни эмас, балки бошқа элементни ўчирмоқчимиз, у ҳолда юқоридаги усулдан фойдалниб бўлмайди.
Навбатни ифодалашга яна бошқача ёндашув, бу массивни чизиқли кетма-кетлик кўринишида эмас, балки боши ва охирига эга бўлган чизиқсиз ёпиқ ҳалқа кўринишда ифодалашдир. Бундан келиб чиқадики, навбатнинг биринчи элементи, охирги элементидан кейиноқ келади. Бу эса агар сўнги элемент банд бўлган тақдирда ҳам биринчи элемент бўш бўлса, унинг ўрнига оҳирги элементдан кейин жойлашади.