СД типа стек

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

При реализации стека рассматриваются стек как отображение на массив и стек как отображение на список.

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

1. Операция инициализации.

2. Операция включения элемента в стек.

3. Операция исключения элемента из стека.

4. Операция проверки: стек пуст / стек не пуст.

5. Операция проверки: стек переполнен / стек не переполнен (данная операция характерна для стека как отображения на массив).

6. Операция чтения элемента (доступ к элементу).

Все операции не зависят от размерности стека, т.е. порядок временной сложности – О(1).

Имеется две модификации стека:

1. Указатель находится на вершине стека, показывая на первый пустой элемент.

2.

слот

Указатель указывает на первый заполненный элемент.

Стек в последовательной памяти (схема на физическом уровне):

S

Дескриптор:

Условные обозначения	Название стека
Нижний адрес стека
Верхний адрес стека
Адрес указателя
Описание элемента

Применение стека:

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

Алгоритм сортировки Хоара (стек используется для хранения границ сортируемой области в таблице):

1. Включить в стек начало и конец сортируемой таблицы.

2. Исключить из стека адрес конца сортируемой области (В). Если стек пуст, то сортировка окончена.

3. Исключить из стека адрес начала сортируемой области (А).

4. Выбираем ключ-разделитель в сортируемой области (при этом используем тот или иной алгоритм).

5. Размещаем меньшие ключи до разделителя, а большие – после него. Адрес разделителя – С.

6. Если А < (С-1), то записываем в стек адрес А и (С-1).

7. Если (С+1) < В, то записываем в стек начало (С+1) и конец сортируемой области В и переходим к п.2.

2) Стек используется при разработке компиляторов.

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

Пример: Имеем выражение (5 + 3) * 7 + 2 * 4. Преобразуем его к виду 5 3 + 7 * 2 4 * +

< > - стек. Заносим в стек цифры и когда появляется операция, то выполняем ее над занесенными в стек элементами: < > ® < 5 > ® < 5 3 > ® < 8 > ® < 8 7 > ® …

3) Cтеки оказали влияние и на архитектуру ЭВМ, послужили основой для стековых машин. В такой ЭВМ аккумулятор выполнен в виде стека, позволяющего расширить спектр безадресных команд.

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

Дата добавления: 2014-01-07