Логическая структура дека

Деки

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

Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.

Над деком определены следующие операции:

* включение элемента справа;

* включение элемента слева;

* исключение элемента справа;

* исключение элемента слева;

* определение размера;

* очистка.

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

Физическая структура дека в статической памяти идентична структуре кольцевой очереди.

Разработать программный пример, иллюстрирующий организацию дека и операции над ним, не сложно по образцу примеров 1.1, 1.3. В этом модуле должны быть реализованы процедуры и функции:

Function DeqWrRight(a: data): boolean; - включение элемента справа;

Function DeqWrLeft(a: data): boolean; - включение элемента слева;

Function DeqRdRight(var a: data): boolean; - исключение элемента справа;

Function DeqRdLeft(var a:data): boolean; - исключение элемента слева;

Procedure DeqClr; - очистка;

Function DeqSize: integer; - определение размера.

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

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