Операції, що здійснюються над чергою:

Для черги визначено три примітивні операції. Операція insert (q,x) поміщає елемент х в кінець черги q. Операція remove(q) видаляє елемент з початку черги q і привласнює його значення змінній х. Третя операція, empty (q), повертає значення true або false залежно від того, чи є дана черга порожньої чи ні. Крім того, враховуючи те, що напівстатична черга реалізується на одновимірному масиві, необхідно стежити за можливістю його переповнення. З цією метою вводиться операція full(q).

Операція insert може бути виконана завжди, оскільки на кількість елементів, які може містити черга, ніяких обмежень не накладається. Операція remove, проте, застосовна тільки до непорожньої черги, оскільки неможливо видалити елемент з черги, що не містить елементів. Результатом спроби видалити елемент з порожньої черги є виникнення виняткової ситуації втрата значущості. Операція empty, зрозуміло, здійснювана завжди.

Приклад реалізації черги у вигляді одновимірного масиву на Паскалі:

const

MaxQ = ...

type

E = ...

Queue = Array [1..MaxQ] E;

var

Q: Queue;

F, R: Integer;

{Покажчик F указує на початок черги. Покажчик R указує на кінець черги. Якщо черга порожня, то F = 1, а R = 0 (Тобто R < F – умова пустоти черги).}

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

begin

Inc(R);

Q[R]:=I;

end;

Function Empty(Q: Queue): Boolean;

begin

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

end;

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

begin

If Not Empty(Q) then

begin

I:=Q[F];

Inc(F);

end;

end;

Приклад роботи з чергою з використанням стандартних процедур.

MaxQ = 5

Проводимо вставку елементів А, B і С в чергу.

Insert(q, А);

Insert(q, B);

Insert(q, С);

Прибираємо елементи А і 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 рівне нулю.

Проте цей метод вельми непродуктивний. Кожне видалення вимагає переміщення всіх елементів, що залишилися в черзі. Якщо черга містить 500 або 1000 елементів, то очевидно, що це неефективний спосіб. Далі, операція видалення елемента з черги логічно передбачає маніпулювання тільки з одним елементом, тобто з тим, який розташований на початку черги. Реалізація даної операції повинна відображати саме цей факт, не проводячи при цьому безлічі додаткових дій.

Інший спосіб передбачає розглядати масив, який містить чергу у вигляді замкнутого кільця, а не лінійної послідовності, що має початок і кінець. Це означає, що перший елемент черги слідує відразу ж за останнім. Це означає, що навіть в тому випадку, якщо останній елемент зайнятий, нове значення може бути розміщено зразу ж за ним на місці першого елемента, якщо цей перший елемент порожній.