2014-02-09
786
Дек
Дек – это структура данных, представляющая собой последовательность элементов, в которой можно добавлять и удалять в произвольном порядке элементы с двух сторон. Первый и последний элементы дека соответствуют входу и выходу дека.
Выделяют ограниченные деки:
- дек с ограниченным входом – из конца дека можно только извлекать элементы;
- дек с ограниченным выходом – в конец дека можно только добавлять элементы.
Данная структура является наиболее универсальной из рассмотренных выше линейных структур. Накладывая дополнительные ограничения на операции с началом и/или концом дека, можно осуществлять моделирование стека и очереди.
Дек также можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру – в виде линейного списка.
Поскольку в деке, как и в очереди, осуществляется работа с обоими концами структуры, то целесообразно использовать те же подходы к организации дека, что применялись и для очереди.
|
|
|
Рисунок 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 – Реализация дека на базе линейного двунаправленного списка
