Дек можно представить в виде звеньев, каждый из которых состоит из трех полей: первое поле – поле элемента, второе – поле ссылки на последующий элемент, третье – поле ссылки на предыдущий. В схеме имеются две ссылки nil, каждая из которых ограничивает движение по деку на его концах. Способ описания используемых типов данных, сравним с очередями, но здесь уже имеются три поля.
UsesCRT; {описание переменных}
Type typeelem=Integer;
connect=^data;
data=Record
elem: typeelem;
Next: connect;
Pred: connect
End;
Процесс вставки звена в дек существенно отличается от ранее рассмотренных случаев. В деке, как и в динамической цепочке общего вида, новый элемент можно вставлять в любом его месте, а, кроме того, учитывая двухстороннюю связь звеньев в деке, можно поставить вопрос о вставке до или после указанного элемента. Отсюда следует, что для вставки элемента в дек необходимо иметь две процедуры: процедуру вставки элемента до заданного звена и процедуру вставки элемента после заданного звена. Вставка звена в дек также сопровождается установлением четырех связей.
Для уменьшения процедур можно использовать вспомогательные процедуры:
Procedureinsert1;
{занесение элемента в дек после заданного звена}
var s1, s2, p:connect;
Begin
s1:=sn1;
s2:=sn2;
while s1^.elem<>y do s1:=s1^.next;
while s2^.pred^.elem<>y do s2:=s2^.pred;
new;
p^.elem:=x;
p^.next:=s2;
p^.pred:=s1;
s2^.pred:=p;
s1^.next:=p;
end;
{процедура Insert1 используется при вставке элемента после заданного звена при условии что это не начало или не конец дека.}
Procedureinsert3;
{занесение элемента в дек до заданного звена}
var s1, s2, p:connect;
Begin
s1:=sn1;
s2:=sn2;
while s1^.next^.elem<>y do s1:=s1^.next;
while s2^.elem<>у do s2:=s2^.pred;
new;
p^.elem:=x;
p^.next:=s2;
p^.pred:=s1;
s2^.pred:=p;
s1^.next:=p;
end;
{процедура Insert3 используется при вставке элемента до заданного звена при условии что это не начало или не конец дека}
Procedureinsert2;
{занесение элемента в дек}
var p:connect;
Begin
if k='к' then begin
new;
p^.next:=nil;
p^.elem:=x;
p^.pred:=sn2;
sn2^.next:=p;
sn2:=p;
end;
if k='н' then begin
new;
p^.pred:=nil;
p^.elem:=x;
p^.next:=sn1;
sn1^.pred:=p;
sn1:=p;
end;
End; {insert}
{Insert2 – вставка элемента в начало или в конец дека}
Используем указатель конца дека: указателю конца дека присваиваем значение нового звена, указателю последнего элемента присваиваем значение нового звена.
Procedureinsertnext;
{занесение элемента x в дек после заданного звена}
var s1, s2, p:connect;
Begin
s1:=sn1; s2:=sn2;
if then insert1
else insert2; end;
В противоположность первого случая, указателю предыдущего элемента присваиваем значение нового звена, указателю конца так же присваиваем значение нового звена.
Procedureinsertpred;
{занесение элемента в дек до заданного звена}
var s1, s2, p:connect;
Begin
s1:=sn1;
s2:=sn2;
if then insert3
else insert2
end;
Рассмотренные процедуры применимы только для деков, имеющих не менее одного звена, поэтому в качестве самостоятельного задания можно дать модификацию данных процедур с учётом ставки звена пустой и одноэлементные деки.
Удаление звена из дека заключается в его изоляции от соседних звеньев. Это означает, что ссылка next предыдущего звена должна быть переадресована на звено, следующее за удаляемым звеном, а ссылка pred – на звено перед удаляемым звеном.
Function remove:typeelem;
{удалениеэлементаиздека}
var p:connect;
Begin
if andthen begin
remove:=s^.elem;
s^.next^.pred:=s1^.pred^.pred;
s^.pred^.next:=s^.next^.next;
end
Else begin
if s=sn1 then begin
p:=s;
remove:=s^.elem;
s^.next^.pred:=nil;
sn1:=s^.next;
dispose;
end;
if s=sn2 then begin
p:=s;
remove:=s^.elem;
s^.pred^.next:=nil;
sn2:=s^.pred;
dispose;
end;
End;
End; {remove}
Если звено первое, то значению функции присваиваем значение первого элемента; если – второе, то – последнего элемента.
Заключение:
Использование динамических структур данных эффективно применять при решении задач, так как каждому значению переменной выделяется какая-то область памяти, в ходе чего происходит учет ресурсов компьютера. При необходимости эту ячейку можно ликвидировать, если информация находящаяся в этой ячейке нам больше не понадобится.
Конечно, при решении задач с помощью статистических переменных обработка и доступ к информации облегчается. При использовании статистических структур данных происходит нерациональное использование оперативной памяти, потому что для статистических переменных выделяется фиксированный размер памяти.
Стековых структур данных, очередей и деков в среде «ТУРБО ПАСКАЛЬ» как тип переменных не существует, поэтому, для наглядности, используют массивы и линейные списки.
Стек как структура данных используется при решении рекурсивных задач, когда необходимо сначала решить последнюю проблему, а уже за ним предыдущие проблемы. Рекурсивные процедуры обращаются сами к себе, при этом изменяются значения переменных, предшествующие значения которых складываются в стек. При выполнении начальной заданной условий, находится решение для простейшей функции, затем более сложной.
Приложение
Стек:
1. Дан стек заполненный случайным образом, из целых чисел. Удалить из него все отрицательные элементы, используя второй стек и одну переменную.
randomize;
init;
init;
for i:=1 to n do
begin
y:=random-random;
push;
end;
list; Writeln;
for i:=1 to n do
begin
push);
pop;
end;
for i:=1 to n do
begin
if stacktop>=0 then
push);
pop;
end;
writeln;
list;
2. Дан стек заполненный целыми числами случайным образом. Удалить из стека все числа не кратные заданному с клавиатуры.
randomize;
init;
init;
for i:=1 to n do
begin
y:=random-random;
push;
end;
list; Writeln;
for i:=1 to n do
begin
push);
pop;
end;
writeln;
readln;
for i:=1 to n do
begin
if) mod f=0 then
push);
pop;
end;
writeln;
list;
3. Дан стек, содержащий целые числа. Используя второй стек, записать в дно стека номер один сумму всех элементов.
randomize;
init;
init;
for i:=1 to n-1 do
begin
y:=random-random;
push;
end;
list; Writeln;
f:=0;
for i:=1 to n-1 do
begin
f:=f+stacktop;
push);
pop;
end;
push;
for i:=1 to n-1 do
begin
push);
pop;
end;
list;
writeln;
4. Удалить из стека, который составлен из целых чисел заданных случайным образом, каждый второй элемент. На дне находится первый элемент.
randomize;
init;
init;
for i:=1 to n do begin
y:=random;
push; end;
list; writeln;
while not emptydo begin
pop;
push);
end;
while not emptydo begin
push); end;
list; writeln;
5. Дан стек из целых чисел, заполненный случайным образом. При помощи второго стека удалить последний отрицательный элемент.
randomize;
init;
init;
for i:=1 to n do begin
y:=random-random;
push; end;
list;
y:=0;
while not empty do begin
if <0) and then begin pop; y:=1; end;
push);
end;
list;
while not empty do
push);
list;
6. Дан стек заполненный элементами типа typeelem. Удалить из стека предпоследний элемент.
randomize;
init;
for i:=1 to n do
begin
y:=random-random;
push;
end;
list; Writeln;
y:=pop;
pop;
push;
list; Writeln;
7. Дан стек заполненный элементами типа typeelem. Удалить из стека первый элемент и поместить его в вершину стека номер один.
randomize;
init;
init;
for i:=1 to n do
begin
y:=random-random;
push;
end;
list; Writeln;
repeat
y:=pop;
push;
until empty;
f:=pop;
repeat
y:=pop;
push;
until empty;
push;
list; Writeln;
8. Дан стек из целых чисел, заполненный случайным образом. Поместить вершину стека в дно, используя вспомогательный стек.
randomize;
init;
init;
for i:=1 to n do
begin
y:=random-random;
push;
end;
list; Writeln;
f:=pop;
repeat
y:=pop;
push;
until empty;
push;
repeat
y:=pop;
push;
until empty;
list; Writeln;
9. Дан стек заполненный случайным образом из целых чисел. Поменять в данном стеке содержимое вершины и дна.
randomize;
init;
init;
for i:=1 to n do
begin
y:=random-random;
push;
end;
list; Writeln;
f1:=pop;
repeat
y:=pop;
push;
until empty;
f2:=pop;
push;
repeat
y:=pop;
push;
until empty;
push;
list; Writeln;
10. Дан стек из целых чисел, заполненный случайными образом. Сравнить сумму положительных элементов с модулем суммы отрицательных элементов.
randomize;
init;
init;
w:=1; w1:=1;
for i:=1 to n do begin
y:=random-random;
push; end;
list;
f:=true;
while not empty do begin
y:=pop;
if y>0 then w:=w*y
else w1:=w1*abs;
push;
end;
if w<w1 then writeln
else writeln;
while not empty do begin
y:=pop;
push; end;
list;
11. Дан стек из целых чисел. Поместить в дно стека сумму модулей всех элементов.
randomize;
init;
init;
for i:=1 to n-1 do