Строение ДСД: набор узлов, объединенных с помощью ссылок. Вид узла: Данные+ссылки на другие узлы. Типы структур: Списки, деревья, графы.
Очередь – это линейная структура данных, в которой
добавление элементов возможно только с одного конца
(конца очереди), а удаление элементов – только с другого конца (начала очереди).
FIFO = First In – First Out
«Кто первым вошел, тот первым вышел».
Операции с очередью:
1)добавить элемент в конец очереди (PushTail = втолкнуть
в конец);
2)удалить элемент с начала очереди (Pop).
type Queue = record
data: array[1..MAXSIZE] of integer;
head, tail: integer;
end;
Добавление:
procedure PushTail( var Q: Queue; x: integer);
begin
if Q.head = (Q.tail+1) mod MAXSIZE + 1
then Exit; { очередь полна, не добавить }
Q.tail := Q.tail mod MAXSIZE + 1;
Q.data[Q.tail] := x;
end;
Снятие:
function Pop ( var S: Queue ): integer;
begin
if Q.head = Q.tail mod MAXSIZE + 1 then begin
Result := MaxInt;
Exit;
end;
Result := Q.data[Q.head];
Q.head := Q.head mod MAXSIZE + 1;
end;
Очередь с помощью списков:
type PNode = ^Node;
Node = record
data: integer;
next: PNode;
end;
type Queue = record
head, tail: PNode;
end;
procedure PushTail( var Q: Queue; x: integer );
var NewNode: PNode;
begin
New(NewNode);
NewNode^.data := x;
NewNode^.next := nil;
if Q.tail <> nil then
Q.tail^.next := NewNode;
Q.tail := NewNode; { новый узел – в конец}
if Q.head = nil then Q.head := Q.tail;
end;
function Pop ( var S: Queue ): integer;
var top: PNode;
begin
if Q.head = nil then begin
Result := MaxInt;
Exit;
end;
top := Q.head;
Result := top^.data;
Q.head := top^.next;
if Q.head = nil then Q.tail := nil;
Dispose(top);
end;
Дек (deque = double ended queue, очередь с двумя концами) – это линейная структура данных, в которой добавление и удаление элементов возможно с обоих концов.
Операции с деком:
1)добавление элемента в начало (Push);
2)удаление элемента с начала (Pop);
3)добавление элемента в конец (PushTail);
4)удаление элемента с конца (PopTail).
Реализация:
1)кольцевой массив;
2)двусвязный список.
22.
