Вопрос 8) Стек и его организация

Организация стека в определенном смысле противоположна орга- низации очереди, поскольку здесь используется доступ по принципу "последней пошел, первый вышел" /такой метод доступа иногда назы- вают методом LIFO/. Представим себе стопку тарелок. Нижняя тарел- ка из этой стопки будет использована последней, а верхняя тарелка /которая была установлена в стопку последней/ будет использована первой. Стеки широко используются в системном программном обеспе- чении, включая компиляторы и интерпретаторы.

Исторически сложилось так, что две основные операции для стека - поместить в стек и выбрать из стека - получили название соответственно "затолкнуть" и "вытолкнуть". Поэтому для реализа- ции стека необходимо создать две функции: "posh" /затолкнуть/, которая помещает элемент в вершину стека, и "pop" / вытолкнуть/, которая выбирает из вершины стека значение. Необходимо также пре- дусмотреть определенную область в памяти, где фактически будет храниться стек. Для этого можно использовать массив или можно вы- делить область памяти, используя средство динамического распреде- ления памяти, предусмотренное в языке Турбо Паскаль. Как и при работе с очередью при выборке значения из стека элемент будет по- терян, если его не сохранить гденибудь в памяти. Ниже приводится общая форма процедур установки в стек и выборки из стека.

Type

  stek=^vs;

  vs=record

         bykba:char;    {буква из строки...}    

         next:stek;    {Указатель на новый элемент стэка}

   end;

var

  a,adr,adr1:stek;  {а-указатель который передвигается по стэку}

  s:string        {adr-указатель начала стэка (ещё называют "вершина стэка")}

  {adr1-вспомогательный указатель, для создания следующего элемента стэка}

  i,n:integer;

Begin

repeat

    Writeln('Введите строку');

    readln(s); {в раздел var надо добавить s:string}

  until length(s)>1;

new(a);

  a^.next:=nil;

  a^.bykba:=s[1];

  adr:=a; {запоминаем адрес первого элемента стэка}

  adr1:=nil;

  n:=length(s);

  for i:=2 to n do

  begin

    new(adr1);

    adr1^.next:=a;

    a:=adr1;

    adr:=a;             {указатель как-бы поднимается вместе с ростом стэка}

    a^.bykba:=s[i];  {присваиваем i-ую букву строки s}

  end;

  a:=adr;

  while a<>nil do

  begin

    Write(a^.bykba);

    a:=a^.next

  end;

  readln;

end.

Вопрос 9) Очереди и их организация

О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.

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

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

Type

TSel=^Sel;

Sel=Record

Inf:integer; // TInf – тип информации об элементе списка

A:TSel; // Адрес следующей ячейки

end;

var sp1,spk: TSel;

I,X,Y,k,a:INTEGER;

//Добавление в конец очереди----------------------------------------------------

Procedure Dobk(var sp1,spk:Tsel;Inf:integer);

begin

inc(x);

if k>=X then

if spk=Nil then begin

New(spk);

Spk^.A:=Nil;

Spk^.Inf:=inf;

Sp1:=spk;

end

else begin

New(spk^.A);

spk:=spk^.A;

spk^.Inf:=Inf;

spk^.A:=Nil;

end;

End;

//Прочесть и стереть информацию из начала очереди-------------------------------

Procedure Red1(var sp1,Spk:Tsel;var Inf:integer);

Var sp:Tsel;

begin

Inf:=sp1.Inf;

sp:=sp1;

sp1:=sp1^.A;

Dispose(sp);

if sp1=nil then spk:=nil;

end;

//Распечатать очередь-----------------------------------------------------------

Procedure Wrt(sp1:Tsel);

Var sp:Tsel;

begin

sp:=sp1;

While sp <> Nil do

begin

Write(sp^.Inf,' ');

sp:=sp^.A;

end;writeln;

end;