If Pempty(Poinsv,Poinf) Then
Begin
End;
Begin
End;
End;
Exit
Begin
Begin
Структура данных очередь. Базовые операции над очередью
END.
Readln(el);
End;
EdelSt(S,Vstek,el);
Begin
End;
AddST(S,Vstek,el)
For i:=1 to 2 do {удалить элементы}
Writeln('yel=',el);
writeln('nel=');
Addst(S,Vstek,el) {добавить элемент}
Рассмотрим порядок выполнения алгоритма решения задачи более подробно.
Добавление пяти элементов в стек. Состояние массива S:
| индекс | |||||
| элементы массива | ‘kk’ | ‘ll’ | ‘mm’ | ‘nn’ | ‘pp’ |
| элементы стека | ‘kk’ | ‘ll’ | ‘mm’ | ‘nn’ | ‘pp’ |
Значение указателя Vstek:=5.
Удалить два элемента из вершины стека. Состояние массива S:
| индекс | |||||
| Элементы массива | ‘kk’ | ‘ll’ | ‘mm’ | ‘nn’ | ‘pp’ |
| Элементы стека | ‘kk’ | ‘ll’ | ‘mm’ |
Значение указателя Vstek:=3.
Добавить один элемент в стек. Состояние массива S:
| индекс | |||||
| Элементы массива | ‘kk’ | ‘ll’ | ‘mm’ | ‘rr’ | ‘pp’ |
| Элементы стека | ‘kk’ | ‘ll’ | ‘mm’ | ‘rr’ |
Значение указателя Vstek:=4.
При моделировании реальных процессов и ситуаций, которые описываются с помощью механизмов обслуживания, например, очередь к врачу или в театральную кассу, машин у светофора, очередь заданий пользователя на их выполнение в ОС, используется структура данных очередь.
Очередь– это упорядоченный набор связанных элементов, которые добавляются к ней с одного конца, а удаляются (выбираются) с другого конца.Принцип построения очереди – «первый вошел» и «первый вышел» (first in, first out – англ. яз.) или сокращенноFIFO.
Основываясь на принципах построения очереди, определим основные базовые операции над ней:
- добавить (разместить) новый элемент в конец очереди;
- выбрать и удалить элемент из начала очереди.
При описании очереди может быть использован одномерный массив. Для создания очереди из элементов массива используются дополнительно две переменные. Одна переменная – Poinf – содержит индекс массива первого элемента очереди, а вторая Poinsv – индекс массива со свободным местом в очереди в каждый текущий момент времени. В начале работы с очередью обе переменные принимают значения Poinf:=1 и Poinsv:=1. Если очередь является пустой, то значения этих переменных равны между собой Poinsv=Poinf.
Например, необходимо смоделировать очередь элементов, которая состоит из символов.
Const maxs=6;
Type och=array[1..maxs] of char; {очередь из символов}
Var Cha:och;
{Для добавления элементов в очередь используется процедура пользователя AddCH}
Procedure AddCH(s:char; Var Cha:och; Var Poinsv:integer);
if Poinsv>maxs then
writeln('Переполнение очереди');
Cha[poinsv]:=el;
Poinsv:=Poinsv+1
В этой процедуре выполняется проверка на переполнение очереди, которая может возникнуть в том случае, когда значение переменной Poinsv становится больше размера массива. При добавлении элемента в очередь значение переменной Poinsv увеличивается на единицу, а на свободное место в очереди в ее конец ставится новый элемент el.
Одним из необходимых условий при удалении элементов из очереди является проверка условия полного отсутствия в ней каких-либо элементов – очередь «пуста». Такую проверку выполняет с помощью функция пользователя Pempty.
Function Pempty(PoinSv,PoinF:integer):boolean;
if Poinsv=PoinF then Pempty:=true {очередь пуста}
else Pempty:=false {в очереди есть элементы}
Для удаления элементов из очереди может быть использована процедура EdelCH. Значение удаляемого элемента присваивается переменной el. После удаления элемента из очереди значение переменной Poinf (указатель на первый элемент в очереди) увеличивается на единицу.
Procedure EdelCH (Var CHa:och; Var Poinsv,Poinf:integer; Var el:char);