Простая очередь
Пример подпрограмм, реализующих стек
Стек как механизм реализации вложенности.
Свойства стека и его практическое применение.
· Стек используется при реализации последовательности вложенных вызовов подпрограмм, т. е. когда одна подпрограмма вызывает другую или саму себя. При вызове подпрограммы адрес возврата (адрес следующей за вызовом команды) запоминается в стеке, и таким образом, при выполнении последовательности вложенных вызовов в стеке создается история вызовов подпрограмм, которая может быть восстановлена в обратном порядке при завершении работы подпрограмм (большинство трансляторов используют стек для реализации механизма вызова подпрограмм).
· Трансляторы также используют стеки при разборе арифметических выражений и вложенных друг в друга конструкций языка. При синтаксическом анализе вложенных друг в друга конструкций языка трансляторы используют магазинные (стековые) автоматы (стек при этом содержит не до конца проанализированные конструкции языка).
2. Свойство стека – относительная адресация его элементов: для элемента, сохраненного в стеке, важно не его абсолютное положение в последовательности (массиве), а положение относительно вершины стека или его указателя.
Unit type_st; { модуль описания типов }
Interface
type
point=^element;
element=record
data: string;
next: point;
end;
Implementation
end.
Unit work_st; { модуль процедур, реализующих работу со стеком }
Interface
uses crt, type_st;
procedure Output( pcur: point); { просмотр элементов стека }
procedure Push(var pcur: point; s: string); { добавление элемента в стек }
procedure Pop(var pcur: point; var s: string); { удаление элемента из стека }
Implementation
procedure Output; { просмотр элементов стека }
var
p: point;
begin
clrscr;
p:=pcur;
repeat
write(p^.data,' ');
p:=p^.next;
until p=nil;
end;
procedure Push; { добавление элемента в стек }
var
p: point;
begin
new(p);
p^.data:=s;
p^.next:=pcur;
pcur:=p;
end;
procedure Pop; { удаление элемента из стека }
var
p: point;
begin
if pcur<>nil then
begin
p:=pcur;
s:=p^.data;
pcur:=p^.next;
dispose( p);
end;
end;
end.
3.2. Организация данных – очередь.
Простая очередь представляет собой организацию данных, заключающуюся в том, что включение элементов в последовательность производится с одного конца этой последовательности, а исключение – с другого, – таким образом, доступ к элементам происходит по принципу FIFO (first in first out): первым пришел – первым вышел.
Примерами использования очередей являются диспетчеризация задач операционной системой, буферизация ввода/вывода и другие.
К базисным операциям над очередью относятся: создание пустой очереди; проверка очереди на пустоту; добавление элемента в конец (начало) очереди; удаление элемента из начала (конца) очереди; извлечение данных, начиная с первого (последнего) элемента очереди.