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

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. д, т.е. команд, не требующих явных заданий адресов операндов. Следствием использования стека является увеличение скорости обработки.

Сд типа очередь.

О

Искл. (“голова”)

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

Вкл.

Искл.

Вкл. (“хвост”)

При реализации очереди рассматриваются очередь как отображение на массив (полустатическая реализация) и очередь как отображение на список.

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

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

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

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

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

5. Операция проверки: очередь переполнена / очередь не переполнена.

В последовательной памяти очередь имеет следующий вид:

1

N

слот

Uk 1

Uk 2

Здесь: Uk 1 – указатель на “голову” (начало) очереди, Uk 2 – указатель на “хвост” (конец) очереди.

Чтобы избежать переполнения, рациональней использовать кольцевую очередь. При этом Uk 1 > Uk 2 или Uk 2 > Uk 1. В случае же если очередь не кольцевая, то всегда Uk 2 > Uk 1. Если очередь пуста или переполнена, то Uk 1 = Uk 2.

Пусть n – текущее состояние очереди, а N – количество элементов в очереди, тогда имеем условие 0  n  N и значение n может являться условием проверки состояния очереди. Операция включения возможна, если n < N, а операция исключения, если n > 0. В случае кольцевой очереди при операции модуля указатели будут меняться следующим образом: Uk 1 = Uk 1 mod N + 1, Uk 2 = Uk 2 mod N + 1.

Схема на физическом уровне СД типа очередь выглядит следующим образом:

Дескриптор:

Условные обозначения	Название очереди
Нижний адрес очереди
Верхний адрес очереди
Указатель начала очереди
Указатель конца очереди
Свойства элементов очереди

Применение очереди:

Очередь используется при передаче данных из оперативной во вторичную память (при этом происходит процедура буферизации: накапливается блок и передается во вторичную память). Наличие буфера обеспечивает независимость взаимодействия процессов между производителем и потребителем (ранжирование задач пользователя). Задачи разделяются по приоритетам: 1) задачи, решаемые в режиме реального времени (высший приоритет) (очередь 1); 2) задачи, решаемые в режиме разделения времени (очередь 2); задачи, решаемые в пакетном режиме (фоновые задачи) (очередь 3). Очереди выполняются последовательно.