Конспект. Динамические структуры. Стек. Очередь



Скачать 102.3 Kb.
страница1/5
Дата28.07.2018
Размер102.3 Kb.
ТипКонспект
  1   2   3   4   5

Конспект. Динамические структуры. Стек. Очередь.

Учитель информатики батракова Л.В.

Стек


Определение: Стек - это данные динамической структуры, которые представляют собой совокупность линейно-связанных однородных элементов, для которых разрешено добавлять или удалять элементы только с одного конца списка, который называется вершиной (головой) стека.
Стек функционирует по принципу LIFO (Last - In - First- Out ) - "последним пришел - первым исключается".

При записи и выборке изменяется только адрес вершины стека. Поэтому каждый стек имеет базовый адрес, от которого производятся все операции со стеком. В случае, когда стек пуст, адреса вершины и основания стека совпадают.

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

Так как язык Pascal не имеет непосредственно типа данных стек, то для его моделирования наиболее подходящими структурами являются массивы (статический стек для моделирования структур заданного размера ) и динамический стек, при этом структура будет помещаться в динамической памяти, и её размер будет ограничен только размером кучи.


Условно стек можно представить в виде стакана с шариками.

Описание стека

Type Tptr=^TElem; {Тип указателя на элемент стека}

TElem = record {Тип элемента стека }

inf :integer; {информационная часть}

link : Tptr; {соединительная часть}



end;

Работа с динамическим стеком

Для работы со стеком необходимо иметь один основной указатель на вершину стека (возьмём идентификатор Top) и один дополнительный временный указатель (возьмём идентификатор P), который используется для выделения и освобождения из памяти элементов стека.


  • Создание стека.

Исходное состояние:







    1. Установка вершины стека Top на созданный элемент:





  • Добавление элемента стека.

    1. Исходное состояние:





    1. Выделение памяти под новый элемент стека. Внесение значения в информационное поле нового элемента и установка связи между ним и "старой" вершиной стека Top:





    1. Перемещение вершины стека Top на новый элемент:





  • Удаление элемента стека.

Исходное состояние








    1. Перемещение указателя вершины стека Top на следующий элемент и освобождение памяти, занимаемой "старой" вершиной стека:


Пример 1. Разместить в стеке 10 символов и распечатать их в обратном порядке.

Hиже приводится пример программы, использующей стек. В ней используются следующие процедуры для работы со стеком:



  • процедура Push(val:real), которая в зависимости от состояния стека создаёт первый или добавляет очередной элемент в вершину стека (английское название push - заталкивать);

  • процедура Pop(var val:real), которая извлекает информацию из вершины стека с последующим освобождением её из памяти (английское название pop - выскакивать ).


Program Stack;

Type Tptr = ^TElem; {Тип указателя на элемент стека}

TElem = record {Тип элемента стека}

inf : char; {информационная часть}

link : Tptr; {соединительная часть}



end;
Var top : tptr; {Указатели на конец стека}

value : char;

i: byte;
Procedure_Pop(var'>Procedure Push(val : char; var Top:Tptr); {Процедура добавления элемента}

Var p : tptr; {Вспомогательный указатель}

Begin

new (p);

p^.inf:=val;

p^.link:=top;

top:=p


End;
Procedure Pop(var val : char; var Top:Tptr); {Процедура удаления элемента}

Var p : tptr; {Вспомогательный указатель}

Begin

val:=top^.inf;

p:=top;

top:=p^.link;



dispose (p)

End;
Begin

new(top); { Создание указателя на вершину стека }

top:=nil;



for i:=1 to 10 do

begin

writeln (' введите символ');

readln (value);

push(value,Top); {добавление элемента в стек}



end;

i:=10;


while top<>nil do {пока не будет достигнут конец стека}

begin

pop(value, Top); {извлечение элемента из стека}



writeln (i,'-й символ - ',value);

dec (i)

end

End.
Пример 2. Ввести с клавиатуры 8 чисел и сформировать из них два стека. В первый поместить числа, которые делятся на 2, а во второй -остальные. Распечатать оба стека.
Type Tptr=^TElem; {Тип указателя на элемент стека}

TElem = record {Тип элемента стека }

inf :integer; {информационная часть}

link : Tptr; {соединительная часть}



end;
Var top1,top2 : tptr; {Указатели на конец стеков}

value : integer;

i: byte;
Procedure Push(val : integer; var top:tptr); {Процедура добавления элемента}

Var p :tptr; {Вспомогательный указатель}

Begin

new (p);

p^.inf:=val;

p^.link:=top;

top:=p


End;
Procedure Pop(var val : integer; var top:tptr); {Процедура удаления элемента}

Var p : tptr; {Вспомогательный указатель}

Begin

val:=top^.inf; p:=top;

top:=p^.link; dispose (p)

End;
Begin

new (top1); {Создание указателя на вершину 1-го стека }

new (top2); { Создание указателя на вершину 2-го стека }

top1:=nil; top2:=nil;



for i:=1 to 8 do

begin

writeln (' введите число'); readln (value);

if value mod 2 =0 then

push(value,top1)



else

push(value,top2)



end;

writeln (' 1-й стек - числа делятся на 2 ');

while top1<>nil do

begin

pop(value,top1);



writeln (value);

end;

writeln (' 2-й стек - - числа не делятся на 2');

while top2<>nil do

begin

pop(value,top2);



writeln (value);

end

End.
Задание. Проверить в выражении баланс открывающихся "(" и закрывающихся ")" скобок.

Идея алгоритма заключается в следующем. Если встречается открывающаяся скобка, то в стек помещают какой-либо символ. Если встречается закрывающаяся скобка, то проверяют состояние стека. При этом возможны следующие ситуации:



  • стек непуст: из стека извлекают один элемент;

  • стек пуст, это свидетельствует о том, что закрывающихся скобок больше чем открывающихся.

После того, как просмотрена вся строка символов, необходимо проверить состояние стека. Если он пуст, то баланс скобок не нарушен. В противном случае - баланса нет.





Поделитесь с Вашими друзьями:
  1   2   3   4   5


База данных защищена авторским правом ©znate.ru 2017
обратиться к администрации

    Главная страница