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

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

Операции над деком:

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

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

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

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

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

· очистка.

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

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

Физическая структура дека в статической памяти идентична структуре кольцевой очереди. Разработать программный пример, иллюстрирующий организацию дека и операции над ним не сложно по образцу примеров 4.1, 4.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; - определение размера.