Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Работа с динамическим стеком
|
|
Для работы со стеком необходимо иметь один основной указатель на вершину стека (возьмём идентификатор Top) и один дополнительный временный указатель (возьмём идентификатор P), который используется для выделения и освобождения из памяти элементов стека.
· Создание стека.
Исходное состояние:
1. Выделение памяти под первый элемент стека и занесение в него информации:
2. Установка вершины стека Top на созданный элемент:
· Добавление элемента стека.
1. Исходное состояние:
2. Выделение памяти под новый элемент стека. Внесение значения в информационное поле нового элемента и установка связи между ним и " старой" вершиной стека Top:
3. Перемещение вершины стека Top на новый элемент:
· Удаление элемента стека.
Исходное состояние
1. Извлечение информации из информационного поля вершины стека Top в переменную Val и установка на вершину стека вспомогательного указателя P:
2. Перемещение указателя вершины стека 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 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) endEnd.
Пример 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); endEnd.
Задание. Проверить в выражении баланс открывающихся " (" и закрывающихся ")" скобок.
Идея алгоритма заключается в следующем. Если встречается открывающаяся скобка, то в стек помещают какой-либо символ. Если встречается закрывающаяся скобка, то проверяют состояние стека. При этом возможны следующие ситуации:
- стек непуст: из стека извлекают один элемент;
- стек пуст, это свидетельствует о том, что закрывающихся скобок больше чем открывающихся.
После того, как просмотрена вся строка символов, необходимо проверить состояние стека. Если он пуст, то баланс скобок не нарушен. В противном случае - баланса нет.