3.1.3 Дек

Дек – это структура данных, представляющая собой последовательность элементов, в которой можно добавлять и удалять в произвольном порядке элементы с двух сторон. Первый и последний элементы дека соответствуют входу и выходу дека.

Выделяют ограниченные деки:

• дек с ограниченным входом – из конца дека можно только извлекать элементы;

• дек с ограниченным выходом – в конец дека можно только добавлять элементы.

Данная структура является наиболее универсальной из рассмотренных выше линейных структур. Накладывая дополнительные ограничения на операции с началом и/или концом дека, можно осуществлять моделирование стека и очереди.

Дек также можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру – в виде линейного списка.

Поскольку в деке, как и в очереди, осуществляется работа с обоими концами структуры, то целесообразно использовать те же подходы к организации дека, что применялись и для очереди.

Рисунок 3.8 – Дек и его организация

Описание элементов дека аналогично описанию элементов линейного двунаправленного списка, где DataType является типом элементов дека. Дополнительно введем два указателя на начало и конец дека:

var

ptrBeginDeck,

ptrEndDeck: PElement;

Основные операции, производимые с деком:

• добавить элемент в начало;

• добавить элемент в конец;

• извлечь элемент из начала;

• извлечь элемент из конца;

• очистить дек;

• проверка пустоты дека.

Реализацию этих операций приведем в виде соответствующих процедур, которые, в свою очередь, используют процедуры операций с линейным двунаправленным списком.

procedure InBeginDeck(NewElem: TypeData;

var ptrBeginDeck: PElement);

{Добавление элемента в начало дека}

begin

InsFirst_LineDoubleList(NewElem, ptrBeginDeck);

end;

procedure InEndDeck(NewElem: TypeData;

var ptrBeginDeck, ptrEndDeck: PElement);

{Добавление элемента в конец дека}

begin

Ins_LineDoubleList(NewElem, ptrBeginDeck, ptrEndDeck);

end;

procedure FromBeginDeck(NewElem: TypeData;

var ptrBeginDeck: PElement);

{Извлечение элемента из начала дека}

begin

if ptrBeginDeck <> nil then begin

NewElem := ptrBeginDeck^.Data;

Del_LineDoubleList(ptrBeginDeck, ptrBeginDeck); {удал-м 1-ый}

end;

end;

procedure FromEndDeck(NewElem: TypeData,

var ptrBeginDeck, ptrEndDeck: PElement);

{Извлечение элемента из конца дека}

begin

if ptrBeginDeck <> nil then begin

NewElem := ptrEndDeck^.Data;

Del_LineDoubleList(ptrBeginDeck, ptrEndDeck); {удаляем конец}

end;

end;

procedure ClearDeck(var ptrBeginDeck: PElement);

{Очистка дека}

begin

while ptrBeginDeck <> nil do

Del_LineDoubleList(ptrBeginDeck, ptrBeginDeck);

ptrEndDeck := nil;

end;

function EmptyDeck(var ptrBeginDeck: PElement): boolean;

{Проверка пустоты дека}

begin

if ptrBeginDeck = nil then EmptyDeck := true

else EmptyDeck := false;

end;

Листинг 3.20 – Реализация дека на базе линейного двунаправленного списка