Вставка структур

Программный пример представляет процедуру, выполняющую вставку элемента в любое место очереди.
{ Вставка элемента в очередь }
const
MAX_EVENT = 100;
type
EvtType = string[80];
var
event: array[1..MAX_EVENT] of EvtType;
spos, rpos, t: integer;
ch:char;
done:boolean;
{ добавить в очередь }
procedure Qstore(q:EvtType);
begin
if spos=MAX_EVENT then
WriteLn('List full')
else
begin
event[spos]:= q;
spos:= spos+1;
end;
end; End.

Извлечение.

Извлечение элемента из очереди выполняется просто. Из массива извлекается первый элемент, и весь массив смещается влево, а последний элемент удаляется.

{ Извлечение элемента из очереди }

function Qretrieve:EvtType;
begin
if rpos=spos then
begin
WriteLn('No appointments scheduled.);
Qretrieve:= '';
end else
begin
rpos:= rpos+1;
Qretrieve:= event[rpos-1];
end;
end;

На практике в односвязных списках используется преимущественно операция удаления элемента, следующего за данным, так как проход по всему списку - слишком дорогостоящая операция. Получается, также, что мы не можем быстро удалить текущий элемент. [2]

Анализ сложности алгоритма

Пространственная сложность – О(n) т.е. линейная зависимость от размера очереди. Удвоение размера задачи удвоит и необходимое время. Сложность обычной вставки О(1) (Устойчивое время работы не зависит от размера задачи).[3]

Класс входных данных, для которых применим алгоритм или структура

Входными данными в данном алгоритме могут выступать любые натуральные числа. При написании программы и её тестирования использовались данные целого типа integer, в диапазоне значений -2147483648 … 2147483647.

Примеры практических задач, где может использоваться данный алгоритм.

Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.

Клавиатурный буфер BIOS организован в виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей: на следующий элемент в нём и на первый незанятый элемент.

Разработка визуализатора.