Динамические структуры данных. Решение задач. Стек. Очередь. Дек

Динамические структуры данных. Решение задач. Стек. Очередь. Дек Курсовая работа "Динамические структуры данных. Решение задач. Стек. Очередь. Дек" Введение Для решения многих практических задач используются структуры данных – массив, запись, множество и так далее. Цель описания типов данных и последующего описания переменных, как относящихся к этому типу, состоит в том, чтобы зафиксировать на время выполнения программы размер значений, которые присваиваются этим переменным и, соответственно, фиксировать размер выделяемой области памяти для них. Такие переменные называются статическими. Вследствие фиксирования размера выделенной памяти возникают определенные трудности: неэффективное использование оперативной памяти. Нам, во многих случаях, заранее не известны значения той или иной переменной, и даже факт существования этого значения. Для решения задач мы можем использовать только статические переменные, но мы не знаем значения результата и его размеры, поэтому нам бы пришлось выделять место в памяти для максимально возможного итогового значения, что приводит к нерациональному использованию памяти машины. Созданные и не описанные заранее, переменные размещаются на свободные участки в динамической области оперативной памяти. Такой способ распределения памяти называется динамическим. Существуют множество типов динамических структур данных, среди них, такие как стек, очередь, линейные списки, деки, деревья и другие. 1. Стек Типичная ситуация, когда одна проблема требует решения другой, которая неразрешима без решения третьей и так далее. В этом ряду проблема, не вызвавшая новых проблем, решается нами первой, хотя оформилась последней, а исходная проблема решается в последнюю очередь. Такая дисциплина обслуживания обозначается LIFOи часто используется в программах. Ей соответствует абстрактная линейная структура, называемая стек. Определение для стека на языке линейного списка: стек – частный случай линейного односвязного списка, для которого разрешено добавлять или удалять элементы только с одного конца списка, который называется вершиной стека. Помещение нового элемента в стек, чтение для обработки и его удаление происходит в одном его конце – верхушке. Другой конец стека неактивен. Если мы удалим элемент, в верхушке оказывается следующий, можно сравнить с действием магазина в стрелковом оружии. Включение нового элемента как бы проталкивает имеющиеся элементы в сторону дна. Порядок их следования при хранении не нарушается, как и в очередях, массивах и других структурах. Поскольку в каждый момент нужен доступ к одному, верхнему, элементу стека, индексы элементов не нужны. Пусть Т – некоторый тип. Рассмотрим тип «стек элементов типа Т». Его значениями являются последовательности значений типа Т. Основные операции, которые используются при применении стека · Сделать пустым; · Добавить элемент; · Взять элемент; · Стек пуст; · Вершина стека: Т; Процедура «сделать пустым» делает стек пустым, то есть «на дне стека ничего нет», рисунок №2. Процедура «добавить элемент» добавляет элемент Х, типа Т, в конец последовательности. S пуста. Выражение «вершина стека» определенно, если последовательность s непустая, и равно последнему элементу последовательности s (. Реализация стека на основе массива Будем считать, что вершина нашего стека – это первый элемент массива, тогда вершина будет находиться всегда в первой ячейке массива, а дно будет продвигаться по массиву. Для удобства договоримся пустым членам массива – свободному стеку присваивать – 1000. Заметно, что стек ограничен по размерам: в него можно записать ограниченное количество элементов Раздел объявления переменных и констант на языке программирования Паскаль выглядит следующим образом: Const n=10; туре typeelem=Integer; { объявление типа переменного } Stack=Array Of typeelem; Var s: stack; Х: typeelem ; I : Integer ; Стек можно моделировать с помощью двух переменных: 1. S – стек. 2. Х – переменная для содержимого вершины. Для того чтобы не было недоразумений и ошибок нужно распечатывать содержимое стека. Эта процедура выводит на экран содержимое стека в виде столбика, на верху которой будет выводиться вершина. В самом нижнем положении будет находиться первый занесённый элемент. Procedure list ; { } Begin Writeln; I : =1; {} While And Do Begin Inc End ; End; Для добавления элемента в стек надо, чтобы этот элемент был типа элемента стека. Процедуру добавления можно описать следующим образом: Procedure push ; Var i : ; {процедура вставки} Begin For i: =n Downto 2 Do s: =s; S : = x End ; { push } Процедура добавления: сначала мы должны освободить место под новый элемент, для этого сдвигаем все элементы стека по массиву вправо и только после добавляем новый в свободную ячейку. влево. В цикле присваиваем I – тому I+1 значение. Последнему члену массива – «дно» стека присваиваем –1000. pop : typeelem ; { считывание с удалением} Var i: Integer; Begin For i: =1 To n-1 Do s: =s; S : =-1000 End ; { pop } stacktop : typeelem ; { считывание без удаления } Begin End; {stacktop} Функция стек пуст: если значение вершины стека не равняется –1000, то функции присваиваем значение логической переменной FALSE . проверка на пустоту } Begin <> -1000 empty: =false; End; init; { процедура инициализации } list; { распечатка содержимого стека } push; { в стек } Writeln; list; { распечатка содержимого стека } х:=stacktop; { } Writeln; Writeln; List; For i: =1 To 2 Do Begin х:=pop; { } End; Writeln; List; х :=pop; Writeln; list; 2. Очередь Очередь – очереди и удаление элемента из начала очереди. Для создания и работы с ней необходимо иметь как минимум два указателя: · На начало очереди. Очередь можно представить в виде звеньев, каждая из которых состоит из двух полей: первое – поле элемента, второе – поле ссылки на следующий элемент очереди. Для очередей применимы следующие операции: · Сделать пустой. · Добавить в очередь. · Взять из очереди. · Очередь пуста. · Очередной элемент. Описание типа переменных для реализации очереди: пользуемся рекурсивным описанием полей: Type typeelem=Integer; тип очереди connect=^data; elem:typeelem; тип информационной ячейки next:connect тип указателя End; Процедура инициализации очереди включает в себя выделение памяти для создания новой ячейки, указатели присваиваются равными новой ячейке, указатель на следующее звено равно nil: Процедура распечатки содержимого очереди: независимой переменной присваиваем значение указателя начала, задаем цикл, до того момента как указатель не будет равен nil; выписываем содержимое звена и указателю задаем значение следующего звена: S: =Sn; While s<>nil do begin Write; Функция проверки на пустоту очереди выглядит следующим образом: Empty : = Sn = SK ; Функция может принимать два значения. Если начало и конец совпадают, то функция равна правде, и наоборот: не совпадают – лжи. new; P ^. Next : = nil ; Sk^. Next: =p; sk := p ; создается новое звено, указатель которого равен nil, информационной ячейке придается какое-то значение, и указатель конца передвигается к этому звену. Remove= Sn^. Elem; ; Sk Для того чтобы не было заполнение памяти ненужной информацией, используют процедуру , которая освобождает память. Remove= Sn^. Elem; Sn: =Sn^. Next; Dispose; Тема №3: деки . Дек как динамическая структура данных включает в себя характерные особенности очереди и стека. Перемещение в очереди осуществляется от ее левого конца к правому, то есть от первого к последнему элементу. В стеке движение также идет в одну сторону, но порядок прохождения элементов обратный – от последнего элемента к первому. Дек же является двунаправленным списком, где движение может осуществляться в обе стороны. Дек, как и очередь, определяется ссылками на свои два конца, однако, в отличие от очереди, можно обрабатывать элементы в начале, в конце и в середине. Дек можно представить в виде звеньев, каждый из которых состоит из трех полей: первое поле – поле элемента, второе – поле ссылки на последующий элемент, третье – поле ссылки на предыдущий. В схеме имеются две ссылки nil , каждая из которых ограничивает движение по деку на его концах. Способ описания используемых типов данных, сравним с очередями, но здесь уже имеются три поля. Uses CRT ; {описание переменных} Type typeelem=Integer; elem: typeelem; Pred : connect End ; двухстороннюю связь звеньев в деке, можно поставить вопрос о вставке до или после указанного элемента. Отсюда следует, что для вставки элемента в дек необходимо иметь две процедуры: процедуру вставки элемента до заданного звена и процедуру вставки элемента после заданного звена. Вставка звена в дек также сопровождается установлением четырех связей. Для уменьшения процедур можно использовать вспомогательные процедуры: Procedure var s1, s2, p:connect; Begin s1:=sn1; <>y do s1:=s1^. next; <>y do s2:=s2^. pred; new; p^. elem:=x; p^. next:=s2; p^. pred:=s1; s2^. pred:=p; s1^. next:= p; end; Insert1 используется при вставке элемента после заданного звена при условии что это не начало или не конец дека.} var s1, s2, p:connect; Begin s1:=sn1; s2:=sn2; <>y do s1:=s1^. next; while s2^. elem<>у new; p^. elem:=x; p^. next:=s2; p^. pred:=s1; s1^. next:= p; end; {процедура Insert3 используется при вставке элемента до заданного звена при условии что это не начало или не конец дека} Procedure insert2; {занесение элемента в дек} var p:connect; Begin if k='к ' then begin new; p^. next:=nil; p^. pred:=sn2; sn2^. next:=p; end; new; p^. pred:=nil; p^. elem:=x; p^. next:=sn1; sn1^. pred:=p; sn1:=p; end; End; {insert} { Insert2 – вставка элемента в начало или в конец дека} {занесение элемента x в дек после заданного звена} var s1, s2, p:connect; Begin else insert2; end; Procedure insertpred; {занесение элемента в дек до заданного звена} Begin end; Рассмотренные процедуры применимы только для деков, имеющих не менее одного звена, поэтому в качестве самостоятельного задания можно дать модификацию данных процедур с учётом ставки звена пустой и одноэлементные деки. Удаление звена из дека заключается в его изоляции от соседних звеньев. Это означает, что ссылка next pred Function remove:typeelem; { удаление элемента из дека } Begin remove:=s^. elem; s^. pred^. next:=s^. next^. next; end Else begin p:=s; s^. next^. pred:=nil; end; if s=sn2 then begin p:=s; remove:=s^. elem; sn2:=s^. pred; dispose; end; End; End; {remove} Если звено первое, то значению функции присваиваем значение первого элемента; если – второе, то – последнего элемента. Использование динамических структур данных эффективно применять при решении задач, так как каждому значению переменной выделяется какая-то область памяти, в ходе чего происходит учет ресурсов компьютера. При необходимости эту ячейку можно ликвидировать, если информация находящаяся в этой ячейке нам больше не понадобится. Конечно, при решении задач с помощью статистических переменных обработка и доступ к информации облегчается. При использовании статистических структур данных происходит нерациональное использование оперативной памяти, потому что для статистических переменных выделяется фиксированный размер памяти. Стек как структура данных используется при решении рекурсивных задач, когда необходимо сначала решить последнюю проблему, а уже за ним предыдущие проблемы. Рекурсивные процедуры обращаются сами к себе, при этом изменяются значения переменных, предшествующие значения которых складываются в стек. При выполнении начальной заданной условий, находится решение для простейшей функции, затем более сложной. Приложение Стек: 1. Дан стек заполненный случайным образом, из целых чисел. Удалить из него все отрицательные элементы, используя второй стек и одну переменную. randomize; init; init; for i:=1 to n do begin y:=random-random; push; end; begin 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; for i:=1 to n do begin pop; end; writeln; begin if) mod f=0 then push); pop; end; list; 3. Дан стек, содержащий целые числа. Используя второй стек, записать в дно стека номер один сумму всех элементов. randomize; init; init; for i:=1 to n-1 do begin y:=random-random; push; end; f:=0; for i:=1 to n-1 do begin push); pop; end; push; begin push); pop; end; list; 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; list; y:=0; while not empty do begin <0) and then begin pop; y:=1; end; push); end; list; while not empty do push); list; 6. Дан стек заполненный элементами типа typeelem. Удалить из стека предпоследний элемент. 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 push; end; list; Writeln; repeat y:=pop; push; until empty; repeat y:=pop; push; push; list; Writeln; 8. Дан стек из целых чисел, заполненный случайным образом. Поместить вершину стека в дно, используя вспомогательный стек. randomize; init; init; for i:=1 to n do begin push; end; list; Writeln; f:=pop; repeat y:=pop; push; 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; f1:=pop; repeat y:=pop; push; until empty; f2:=pop; push; repeat push; until empty; push; 10. Дан стек из целых чисел, заполненный случайными образом. Сравнить сумму положительных элементов с модулем суммы отрицательных элементов. randomize; init; init; for i:=1 to n do begin y:=random-random; list; f:=true; while not empty do begin y:=pop; if y>0 then w:=w*y else w1:=w1*abs; push; end; <w1 then writeln else writeln; while not empty do begin push; end; list; 11. Дан стек из целых чисел. Поместить в дно стека сумму модулей всех элементов. randomize; init; init; begin push; end; list; Writeln; f:=0; begin f:=f+abs); pop; end; push; for i:=1 to n-1 do begin push); pop; end; list; writeln; 12. Дан стек из целых чисел. Поместить в дно стека произведение всех элементов. randomize; init; init; for i:=1 to n-1 do begin y:=random-random; push; end; list; Writeln; f:=1; begin f:=f*abs); push); pop; end; push; for i:=1 to n-1 do begin pop; end; list; writeln; 13. Дан стек, заполненный случайными числами. Вычесть из всех элементов стека число вводимое с клавиатуры. Используйте второй стек для хранения данных. init; init; begin y:=random-random; push; end; list; Writeln; Writeln; readln; begin push; pop; end; push; for i:=1 to n do begin push); pop; end; list; 15. В стек записаны элементы типа typeelem. Записать содержимое стека в обратном порядке в тот же стек. Используйте два вспомогательных стека. randomize; init; init; init; begin y:=random-random; push; end; list; Writeln; for i:=1 to n do begin pop; end; for i:=1 to n do begin push); pop; end; for i:=1 to n do begin push); pop; end; list; init; init; init; push; while not emptydo begin push); end; while not or empty) do begin push); end; list; 17. Стек заполнен элементами типа typeelem. Записать в этот же стек сначала элементы с четными номерами, затем – с нечетными. init; init; init; for i:=1 to n do push; while not emptydo begin push); end; while not or empty) do push); while not or empty) do push); list; 18. Стек заполнен целыми числами случайным образом. Записать в стек сначала четные элементы, затем – нечетные. Для решения задачи используйте два дополнительных стека. randomize; init; init; init; for i:=1 to n do begin y:=random; push; end; list; Writeln; while not emptydo if stacktop mod 2=0 then push) else push); while not emptydo push); list; нужное количество стеков. randomize; init; init; init; init; for i:=1 to n do begin y:=random; push; end; while not emptydo begin while not emptydo begin >=stacktop then else push); end; while not emptydo end; while not emptydo list; Writeln; 20. Отсортировать стек, заполненный целыми числами, по убыванию. На дне стека должен быть максимальный элемент, в вершине – минимальный. Использовать только нужное количество стеков. 21. Дан стек, заполненный случайными целыми числами. Удалить из стека повторяющиеся элементы, оставив по одному. init; init; init; init; begin push; end; while not emptydo begin push); while not emptydo if stacktop=stacktop then pop else push); while not emptydo push); end; while not emptydo push); list ; Writeln ; 22. Удалить из стека, который состоит из целых чисел, все числа, которые не повторяются. 23. Стек заполнен однозначными и двухзначными числами. Поместить однозначные числа в один стек, двухзначные – в другой. randomize; init; init; init; for i:=1 to n do begin y:=random; push; end; while not emptydo if stacktopdiv 10=0 then push) else push); list; Writeln; list; Writeln; 24. Дан стек, заполненный случайным образом целыми числами. Поместить четные элементы в один стек, нечетные – во второй. init; push; y:=0; y:=y+stacktop; push; end; list; init; init; init; for i:=1 to n-1 do begin y:=random-random; push; end; if stacktop<=stacktop then begin push); push) end else push); push); while not emptydo push); writeln; list; 27. Найти в стеке, составленном из целых чисел, максимальный элемент и поместить его в дно стека. 28. В стеке, составленном из целых чисел, найти минимальный элемент и поместить его в вершину стека. init; init; init; for i:=1 to n-1 do begin y:=random-random; push; end; while not emptydo if stacktop<=stacktop then begin push); push) end while not emptydo push); push ); ; list; 30. Дан стек, заполненный случайным образом целыми числами. Отыскать в данном стеке максимальный и минимальный элементы. Переместить максимальный элемент в дно стека, минимальный – в вершину. randomize; init; init; init; for i:=1 to n-1 do begin y:=random-random; push; end; if stacktop<=stacktop then begin push); push) end else push); push); push); while not emptydo if stacktop>=stacktop then begin push); push) end while not emptydo writeln; list; Дек: 1. Дан дек из целых чисел, заполненный случайным образом. В начало дека вставить число, вводимое с клавиатуры. 2. Дек состоит из целых чисел. Вставить в этот дек ноль после числа вводимого с клавиатуры. 3. Заполнить дек целыми положительными числами. Вставить в дек сегодняшнее число до элемента, который равен числу вводимому с клавиатуры. 4. Заполнить дек случайным образом целыми числами. Найти максимальный элемент в образовавшемся деке и вставить до и после него ноль. 5. Дан дек, заполненный случайным образом. До после минимального элемента вставить тысячу. 6. В деке, состоящем из целых чисел, вставить перед предыдущим элементом, равным введенному числу с клавиатуры, число равное произведению элемента и предыдущего элемента. 7. Дек заполнен случайными целыми числами. Сортировать данный дек по возрастанию. 10. Найти сумму всех элементов дека, который состоит из целых чисел, и приписать эту сумму в начало дека. 11. Дек заполнен случайным образом целыми числами. Найти в деке максимальный и минимальный элементы и поменять их местами. 12. Дан дек, заполненный целыми положительными и отрицательными числами. Найти в данном деке отрицательные элементы и удалить их. 14. Удалить нечетные элементы в деке, который заполнен целыми числами. 15. Найти в данном деке, заполненном случайным образом, отрицательные элементы, удалить эти элементы и вставить вместо них модули удаленных. 16. Дек состоит из целых отрицательных и положительных чисел, заданных случайным образом. Найти и записать вместо положительных элементов, равные им по модулю отрицательные числа. 17. Перед отрицательными элементами данного дека, который состоит из целых отрицательных и положительных чисел, вставить их модули. 18. После каждого элемента дека вставить сумму всех элементов дека. Дек состоит из целых чисел. 20. Дан дек из целых чисел, заданных случайным образом. Оставить в деке только двухзначные числа, все остальные удалить. 21. Удалить из дека нечетные отрицательные числа. Дек заполнен случайным образом целыми числами. 22. Дек заполнен целыми положительными и отрицательными числами. Удалить из дека все положительные четные числа. 23. Дек состоит из целых чисел, заданных случайным образом. Переписать дек в обратном порядке. 24. В деке находятся целые числа. Добавить в дек столько элементов, чтобы он стал в два раза длиннее и симметричным, то есть: первый элемент был равен последнему, второй – предпоследнему и так далее. то удалить из него средний. 26. Дан дек из целых чисел, заданных случайным образом. Если дек содержит четное количество элементов, то добавить в середину дека минимальный элемент; если же дек содержит нечетное количество элементов, то удалить из него средний. 1. Дана очередь из целых чисел. Удалить из нее все отрицательные элементы. 4. Очередь заполнена случайным образом целыми числами. Добавить в начало очереди произведение всех элементов. 5. Вычесть из всех элементов очереди число вводимое с клавиатуры. 6. Прибавить ко всем элементам число вводимое с клавиатуры. Очередь заполнена целыми числами. 7. Записать очередь в обратном порядке. Очередь заполняется с клавиатуры. 8. Дана очередь из целых чисел. Удалить из нее числа кратные заданному с клавиатуры числу. 10. Дана очередь из целых чисел. Поменять в очереди первый элемент со вторым, третий с четвертым и так далее до конца очереди. 11. В начало очереди поместить элементы с четными номерами, а вконец – с нечетными. 12. Очередь состоит из целых чисел. Поместить в начало очереди четные, а вконец – нечетные элементы. Основные процедуры: Стек: {Реализация стека на основе массива} Program st; Uses Crt; Const n=10; Type typeelem=Integer; stack=Array Of typeelem; Var s:stack; y:typeelem; i: Integer; {создание стека } Var i: Integer; Begin Procedure list; {распечатка содержимого стека } Var i: Integer; Begin Writeln; i:=1; End; {list} Procedure push; {занесение элемента в стек } Var i: Integer; Begin For i:=n Downto 2 Do s:=s; s:=x End; {push} {удаление элемента из стека } Begin pop:=s; For i:=1 To n-1 Do s:=s; s:=-1000 End; {pop} Function stacktop:typeelem; {считывание верхнего без удаления } Begin stacktop:=s Function Boolean; {проверка стека на пустоту} Begin End; {empty} {–} Begin {main} init; list; Writeln; Writeln; list; Writeln); y:=stacktop; Writeln; Writeln; For i:=1 To 2 Do Begin y:=pop; Writeln End; Writeln; list; Writeln; y:=pop; Writeln; Writeln; list; Readln End. {main} Очередь: Program spisok; Uses Crt; connect=^data; data=Record elem:typeelem; next:connect End; Var sn, s, sk:connect; x:typeelem; i: Integer; Procedure init; очереди } var p:connect; Begin new; End; {init} Procedure list; {распечатка содержимого очереди} var s:connect; begin s:=sn^. next; while s<>nil do begin write; End; {list} Function Boolean; Begin empty:=sn=sk; End; {empty} Procedure insert; {занесение элемента x в очередь} Begin new; p^. next:=nil; p^. elem:=x; sk^. next:=p; End; {insert} Function remove:typeelem; {удаление элемента из очереди} Begin remove:=sn^. next^. elem; sn:=sn^. next; End; {remove} {–} Begin ClrScr; randomize; init; {инициализация } for i:=1 to 5 do begin x:=random-random; insert; {вставка элемента в очередь} end; x:=remove; {удаление элемента из очереди} list; writeln; {распечатка содержимого очереди} Readln; End. Дек: {pеализация дека на основе линейного списка} Type typeelem=Integer; data=Record elem:typeelem; pred:connect End; Var sn1, sn2, s:connect; x, y:typeelem; i: Integer; Procedure init; {создание дека } var p:connect; Begin new; p^. pred:=nil; p^. elem:=x; sn1:=p; End; { init} Procedure listnext; {распечатка содержимого дека в прямом порядке} var s:connect; begin s:=sn1; while s<>nil do begin write; s:=s^. next; end; write; list} Procedure {распечатка содержимого дека в обратном порядке} var s:connect; begin s:=sn2; while s<>nil do begin write; s:=s^. pred; end; write; End; {list} {проверка дека на пустоту} Begin empty:=sn1=sn2; End; { empty} Procedure {занесение элемента x в дек после заданного звена} var s1, s2, p:connect; Begin s1:=sn1; while s1^. elem<>y do s1:=s1^. next; <>y do s2:=s2^. pred; new; p^. elem:=x; p^. next:=s2; p^. pred:=s1; s2^. pred:=p; s1^. next:=p; end; Procedure insert3; {занесение элемента x в дек до заданного звена} var s1, s2, p:connect; Begin s1:=sn1; s2:=sn2; while s1^. next^. elem<>y do s1:=s1^. next; <>y do s2:=s2^. pred; new; p^. elem:=x; p^. next:=s2; p^. pred:=s1; s2^. pred:=p; s1^. next:=p; end; Procedure insert2; var p:connect; Begin if k='к new; p^. next:=nil; p^. elem:=x; sn2^. next:=p; end; if k='н ' then begin new; p^. pred:=nil; p^. elem:=x; p^. next:=sn1; sn1:=p; end; End; {insert} Procedure insertnext; {занесение элемента x в дек после заданного звена} var s1, s2, p:connect; Begin s1:=sn1; else insert2 end; Procedure insertpred; {занесение элемента x в дек до заданного звена} Begin s1:=sn1; s2:=sn2; if then insert3 else insert2 end; Function remove1: typeelem; {удаление элемента из начала} Begin remove1:=sn1^. elem; sn1^. next^. pred:=nil; sn1:=sn1^. next; End; {remove} remove2: typeelem; {удаление элемента из конца} Begin sn2^. pred^. next:=nil; sn2:=sn2^. pred; End; {remove} Function remove:typeelem; {удаление из дека } var s1, s2, s, p:connect; Begin s1:=sn1; s2:=sn2; if andthen begin while s1^. next^. elem<>y do s1:=s1^. next; <>y do s2:=s2^. pred; remove:=s1^. next^. elem; s1^. next:=s1^. next^. next; s2^. pred:=s2^. pred^. pred; end else if then remove:=remove2 else remove:=remove1; End; {remove} {–} Begin ClrScr; sn1:=nil; sn2:=nil; k:='к '; init; insert2; writeln; listpred; writeln; insertnext; listnext; insertpred; writeln; remove1; writeln; writeln; listpred; listnext; writeln; listpred; Readln End. стек дек очередь переменная 2. Бабушкина И. А., Бушмелева Н. А., Окулов С. М., Черных С. Ю. Конспекты по информатике. – Киров, 1997. 3. Грэхем Р., Кнут Д., Паташник О. Конкретная информатика. – М.: Мир, 1988. 5. Райнтли, Абстракция и структура данных. 6. Зубов В. С., Справочник программиста. – 1999.