2.15.3. Стек

Наиболее часто встречающаяся динамическая структура данных – стек (магазин) отличается от очереди тем, что она организована по принципу LIFO (last in  first out): «последним пришел  первым ушел».

Стек – это частный случай линейного односвязного списка, для которого разрешено добавлять или удалять элемент только с одного конца списка, который называется вершиной (головы) стека.

Стек можно представить в ввиде трубы с одним запаяным концом, куда помещаются «бочонки» - элементы:

Вершина стека

Добавить

Взять

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

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

Стек можно представить в виде динамической цепочки звеньев. Вершиной является первое звено цепочки (или последнее), заглавное звено становится излишним. Поэтому значением указателя, представляющего стек как единый объект, является ссылка на вершину стека. Каждое звено содержит ссылку на следующее звено цепочки, причем "дно" стека имеет ссылку NIL:

Если стек пуст, то значением указателя р является ссылка NIL. К началу использования стека его необходимо сделать пустым (p=NIL).

Операции над стеком:

1) Занесение элемента в стек.

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

Пример создания и удаление стека из 10 элементов:

Program stack; stack.pas

Uses crt;

Type ptr = ^elem;

elem = record

inf: integer;

next: ptr

end;

Var

Результаты

х = 10

х = 9

х = 8

х = 7

х = 6

х = 5

х = 4

х = 3

х = 2

х = 1

Top: ptr;

x: integer;

i: byte;

Procedure Push(val:integer); {Добавление элемента}

Var pt: ptr;

Begin

new(pt);

pt^.inf:=val;

pt^.next:=Top;

Top:=pt

End;

Procedure Pop(Var Val:integer); {Извлечение }

Var pt: ptr;

begin

val:=Top^.inf;

pt:=Top;

Top:=pt^.next; dispose(pt)

end;

BEGIN

clrscr;

Top:=nil; {Начальная установка указателей}

for i:=1 to 10 do Push(i); {Создание стека из 10 элементов. Удаление стека с

распечаткой значений его элементов}

while Top<>nil do

begin

Pop(x);

writeln('x=',x:4)

end

END.

3. Практическое программирование Этапы подготовки и решения задач на компьютере

Практика программирования показывает, что решение прикладных, инженерных, экономических и научных задач на ЭВМ сложный и трудоемкий процесс, состоящий из следующих этапов:

1. Постановка задачи состоит в четком изложении условия задачи и определении подзадач.

2. Физический и математический анализ. Анализируется, существует ли вообще решение данной задачи и единственно ли оно. Подбирается математический аппарат, и строится математическая модель для решения задачи. Выбирается метод или методика решения (составляются формулы, определяются правила, связывающие эти формулы)

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

Расчленение алгоритма на составные части называется структуризацией.

4. Этап программирования.

Выбирается язык и (или) система программирования, и в соответствии с алгоритмом разрабатывается программа на конкретном языке программирования.

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

6. Решение задач на компьютере.

7. Обработка результатов решения задач. Производится анализ результатов, строятся таблицы, графики, делаются выводы.

Дополнительно могут присутствовать такие этапы как описание структуры программы, описание структур данных, оптимизация программы, этап документирования.

Готовая программа в компьютере проходит следующие стадии

Исходный

модуль

Трансляция  преобразование программы, представленной на одном языке программирования, в эквивалентную форму на другом языке.

Компиляция  трансляция программы с исходного модуля в объектный (или на язык низкого уровня, близкого к машинному языку).

Редактирование связей (компоновка)  изменение порядка размещения, формата и содержимого данных, сборка программы с другими модулями и стандартными подпрограммами.

Загрузка  пересылка программы с носителя данных в основную память и из основной в регистровую.

Исходный модуль  программа на языке высокого уровня.

Объектный модуль  текст программы после компиляции (в машинных кодах с относительными адресами).

Абсолютный модуль  это программа в машинных кодах с подсоединёнными к ней подпрограммами и настроенная на выполнение в заданной области оперативного запоминающего устройства.

Компилятор – программное средство, выполняющее компиляцию программы.

Транслятор  программа или специальное технические средство, выполняющее трансляцию программы.

Редактор связей  программа, предназначенная для построения одного загрузочного модуля из одного или более независимо транслируемых объектных или загрузочных модулей.

Загрузчик  обрабатывающая программа, выполняющая загрузку абсолютного модуля в основную память по установленным адресам.

Различают следующие системы подготовки  и выполнения программы:

1) компилирующего типа (статистическая подготовка) (СИ, ПАСКАЛЬ);

2) интерпретирующего типа (динамическая подготовка).

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

В системах интерпретирующего типа последовательно читается, транслируется и сразу же выполняется оператор за оператором (БЕЙСИК).

Интерпретатор  вид транслятора, осуществляющего пооператорную (покомандную) обработку и выполнение исходной программы.