Деки в вычислительных системах

Деки

Дек (от англ. deq – double ended queue, т.е. очередь с двумя концами) – особый вид очереди в котором включение и исключение элементов может осуществляться с любого из двух концов списка. Частный случай – дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры деки аналогичны структурам кольцевой FIFO-очереди.

Операции над деком заключаются в определении размера, очистки, включение/исключение элемента справа/слева. На рис. 5.2 в качестве примера показана последовательность состояний дека при включении и удалении пяти элементов. На каждом этапе стрелка указывает, с какого конца дека (левого или правого) осуществляется включение или исключение элемента. Элементы соответственно обозначены буквами A, B, C, D, E.

Рис. 5.2. Состояния дека в процессе изменения.

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

В распоряжении пользователя имеются операции QUEUE – запись строки в конец буфера и PULL – выборка строки из начала буфера. Дополнительная операция PUSH – запись строки в начало буфера – превращает буфер в дек с ограниченным выходом. Такая структура буфера ввода позволяет программировать на REXX весьма гибкую конвейерную обработку с направлением выхода одной программы на вход другой и модификацией перенаправляемого потока.

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