Динамические структуры данных: стеки, очереди, деки

Лекция 6. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ: СТЕКИ, ОЧЕРЕДИ, ДЕКИ.

Множество линейных списков может классифицироваться:

- с точки зрения упорядоченности,

- по типу используемой структуры хранения,

- по применению соответствующей логической структуры.

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

- логическая концепция списка,

- варианты структуры хранения для соответствующих типов списков,

- характерные для данного типа списков базовые операции,

- возможности использования структуры для прикладных задач.

СТЕКИ.

Одной из важных и полезных концепций, используемых в вычислительной технике является концепция стека.

СТЕКОМ называется линейный список, в котором размещение новых элементов и удаление существующих производится только с одного конца, называемого вершиной стека (рис.6.1)

Вершина стек Недоступные элементы стека

Размещение                                                                                               Извлечение и просмотр элемента                                                                                                       элемента

 

Рисунок 6.1

Простейшим примером использования стека является задача правильности использования различных типов скобок в выражении. Пусть задано некоторое выражение, содержащее три типа скобок "()","{}","[]":

{x+(y-[a+b])*c-[(d+c])}/(h-(j-k-(1-n]))).

Нужно проверить выполнение трех требований:

а) число левых и правых скобок каждого типа одинаково;

б) каждой правой закрывающейся скобке предшествует левая открывающаяся;

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

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

- вершина стека по типу не соответствует очередной закрывающейся скобке (нарушено требование "в"),

- очередной закрывающейся скобке соответствует пустой стек (нарушены условия "а" или "б").

Программная  реализация стека предполагает выбор рациональной структуры хранения и программную реализацию следующих базовых операций:

-операция включения элемента в стек push(s,i),

- операция удаления элемента из стека pop(s),

- проверка стека на пустоту empty(s),

- операция считывания (выбора) верхнего элемента pick(s).

Здесь s - идентификатор стека, i - идентификатор переменной, хранящей значение включаемого элемента.

В качестве структуры хранения для стека может использоваться массив или связанный список.

1-тип структуры хранения:

ST(s) - <идентификатор массива, число элементов в стеке>.

Тип элемента массива соответствует типу информационной части записи списка.

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

2-тип структуры хранения:

ST(s) - <указатель на первый элемент списка>.

Вершина стека соответствует первому элементу списка, пустой стек соответствует пустому указателю.

Реализация функций стека стека для структуры хранения первого типа требует проверки исключительных ситуаций:

pop(s) - стек пуст (исключительная ситуация, присущая структуре данных);

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

- логической концепцией структуры данных;

- выбором структуры хранения;

- ресурсными ограничениями вычислительной системы.

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

Существует два важных условия, которые должны удовлетворяться в любой рекурсивной процедуре:

- каждый раз, когда процедура обращается к самой себе, она должна в некотором смысле приближаться к решению;

- должен существовать критерий для прекращения процесса вычисления.

Общая схема рекурсивной процедуры при ее построении и компиляции включает три блока (рис 6.2):

- пролог,

- тело,

- эпилог.