53 Динамические структуры данных. Списки. Очередь, стек

Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью).

Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера.

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

Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти.

Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом.

Список (list) – набор элементов, расположенных в определенном порядке.

Таким набором быть может ряд знаков в слове, слов в предложений в книге.

Этот термин может также относиться к набору элементов на диске.

Использование при обработке информации списков в качестве типов данных

привело к появлению в языках программирования средств обработки списков.

Очередь (queue) — линейный список, в котором все включения

производятся на одном конце списка, а все исключения (и обычно всякий

доступ) делаются на другом его конце.

Очередь — тип данных, при котором новые данные располагаются следом за

существующими в порядке поступления; поступившие первыми данные при этом

обрабатываются первыми.

Стек (stack) — линейный список, в котором все включения и исключения

(и обычно всякий доступ) делаются в одном конце списка.

Стек — часть памяти ОЗУ компьютера, которая предназначается для

временного хранения байтов, используемых микропроцессором; при этом

используется порядок запоминания байтов «последним вошел – первым вышел»,

поскольку такие ввод и вывод организовывать проще всего, также операции

осуществляются очень быстро. Действия со стеком производится при помощи

регистра указателя стека. Любое повреждение этой части памяти приводит к

фатальному сбою.

Стек в виде списка (pushdown list) – стек, организованный таким

образом, что последний вводимый в область памяти элемент размещается на

вершине списка.