Простая очередь

Пример подпрограмм, реализующих стек

Стек как механизм реализации вложенности.

Свойства стека и его практическое применение.

· Стек используется при реализации последовательности вложенных вызовов подпрограмм, т. е. когда одна подпрограмма вызывает другую или саму себя. При вызове подпрограммы адрес возврата (адрес следующей за вызовом команды) запоминается в стеке, и таким образом, при выполнении последовательности вложенных вызовов в стеке создается история вызовов подпрограмм, которая может быть восстановлена в обратном порядке при завершении работы подпрограмм (большинство трансляторов используют стек для реализации механизма вызова подпрограмм).

· Трансляторы также используют стеки при разборе арифметических выражений и вложенных друг в друга конструкций языка. При синтаксическом анализе вложенных друг в друга конструкций языка трансляторы используют магазинные (стековые) автоматы (стек при этом содержит не до конца проанализированные конструкции языка).

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): первым пришел – первым вышел.

Примерами использования очередей являются диспетчеризация задач операционной системой, буферизация ввода/вывода и другие.

К базисным операциям над очередью относятся: создание пустой очереди; проверка очереди на пустоту; добавление элемента в конец (начало) очереди; удаление элемента из начала (конца) очереди; извлечение данных, начиная с первого (последнего) элемента очереди.