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

метки: Динамический, Данные, Элемент, Структура, Целое, Число, Звено, Integer

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

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

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

В некоторых случаях решение задачи эффективней при использовании стеков, в других деревьев, в-третьих, – следующих. В этой работе неполный обзор стеков, очередей и деков.

1. Стек

Типичная ситуация, когда одна проблема требует решения другой, которая неразрешима без решения третьей и так далее. В этом ряду проблема, не вызвавшая новых проблем, решается нами первой, хотя оформилась последней, а исходная проблема решается в последнюю очередь. Такая дисциплина обслуживания обозначается LIFO и часто используется в программах. Ей соответствует абстрактная линейная структура, называемая стек.

Определение для стека на языке линейного списка:

стек –

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

Символьный тип данных

... типа данных 28. Chr (n ) в некотором смысле обратна функции Ord : для заданного числового аргумента n она возвращает символ с соответствующим номером. Для символьных ... они исключительно п Значение стека как структуры данных в программировании не исчерпывается лишь стеком отложенных заданий. В ... разделе мы рассмотрим различные алгоритмы решения задачи сортировки. Задача сортировки ставится следующим ...

Пусть Т – некоторый тип. Рассмотрим тип «стек элементов типа Т». Его значениями являются последовательности значений типа Т. Основные операции, которые используются при применении стека

• Сделать пустым;

·Добавить элемент;

• ·Взять элемент;
• ·Стек пуст;
• ·Вершина стека: Т;
• Процедура «сделать пустым» делает стек пустым, то есть «на дне стека ничего нет», рисунок №2.

Процедура «добавить элемент» добавляет элемент Х, типа Т, в конец последовательности.

Процедура «взять элемент» применима, если последовательность S непустая, она забирает из неё последний элемент, который становится значением переменной т.).

Выражение «стек пуст» истинно, если последовательность S пуста. Выражение «вершина стека» определенно, если последовательность s непустая, и равно последнему элементу последовательности s (.

Реализация стека на основе массива

Будем считать, что вершина нашего стека – это первый элемент массива, тогда вершина будет находиться всегда в первой ячейке массива, а дно будет продвигаться по массиву. Для удобства договоримся пустым членам массива – свободному стеку присваивать – 1000.

Заметно, что стек ограничен по размерам: в него можно записать ограниченное количество элементов

Раздел объявления переменных и констант на языке программирования Паскаль выглядит следующим образом:

• Const n=10;
• туре typeelem=Integer; {

Stack=Array Of typeelem;

• Var s: stack;
• Х:typeelem;

I : Integer;

Стек можно моделировать с помощью двух переменных:

1. S – стек.
2. Х – переменная для содержимого вершины.

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

Procedure

Var i: Integer;

Begin

Writeln;

I: =1; { указатель вершины ставится на вершину стека}

While And Do Begin

Writeln;

Inc

End;

End; {list}

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

Procedure

Var i : Integer; {процедура вставки}

Begin

For i: =n Downto 2 Do s: =s;

S: =x

End; {push}

Процедура добавления: сначала мы должны освободить место под новый элемент, для этого сдвигаем все элементы стека по массиву вправо и только после добавляем новый в свободную ячейку.

Функция «взять элемент» в переменную заключена в том, чтобы считать элемент в переменную и удалить его из стека. Функции мы присваиваем значение вершины стека, после чего сдвигаем весь стек на одну ячейку влево. В цикле присваиваем I – тому I+1 значение. Последнему члену массива – «дно» стека присваиваем –1000.

Организационная культура как элемент управления организацией

... понятие, характеристику и эффективность управления организацией, изучить формирование организационной культуры. Глава 1. Организационная культура как элемент управления организацией 1.1 Понятие и характеристика организационной культуры Новые условия хозяйствования, динамизм внешних условий, повышение ...

Function pop : typeelem; { считывание с удалением}

Var i: Integer;

Begin

Pop: =s;

For i: =1 To n-1 Do s: =s;

S: =-1000

End; { pop }

Функция вершина стека: значению функции присваиваем значение вершины стека.

Function stacktop : typeelem; { считывание без удаления }

Begin

Stacktop: =s

End; {stacktop}

Функция стек пуст: если значение вершины стека не равняется –1000, то функции присваиваем значение логической переменной FALSE .

Function empty: Boolean; {

Begin

If s <> -1000 empty: =false;

End; {empty}

В основной программе используются выше указанные процедуры, например:

init; { процедура инициализации }

list; { распечатка содержимого стека }

For i: =1 To 3 Do

push; { вставка в стек }

Writeln;

list; { распечатка содержимого стека }

Writeln);

• х:=stacktop; {

Writeln;

Writeln;

List;

For i: =1 To 2 Do Begin

х:=pop; {считывание с удалением }

Writeln

End;

Writeln;

List;

х:=pop;

Writeln;

Writeln;

list;

Writeln);

— Недостаток реализации стека на основе массива – это его ограниченность в длине, для преодоления этого недостатка используют стек на основе линейного списка.

2. Очередь, Очередь –

• На начало очереди.
• На конец очереди.

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

Для очередей применимы следующие операции:

• Сделать пустой.
• Добавить в очередь.
• Взять из очереди.
• Очередь пуста.
• Очередной элемент.

Реализация очереди на основе линейного списка

Описание типа переменных для реализации очереди: пользуемся рекурсивным описанием полей:

Type typeelem=Integer; тип элемента очереди

connect=^data; рекурсивное определение указателя

data=Record

elem:typeelem; тип информационной ячейки

next:connect тип указателя

End;

В этом случае каждое звено содержится в указателе предыдущего звена.

Развитие композиционных навыков у учащихся среднего звена средствами ...

... звена. 3. Раскрыть особенности работы по созданию тематической композиции. 4. Провести опытно-экспериментальную работу, ориентированную на развитие и формирование композиционных навыков в процессе тематического рисования учащимися среднего звена общеобразовательной школы. ... искусства по законам искусства изложены в концепции художественного образования Б.М. Неменского. Однако работы, целостно ...

Процедура инициализации очереди включает в себя выделение памяти для создания новой ячейки, указатели присваиваются равными новой ячейке, указатель на следующее звено равно nil:

• Процедура распечатки содержимого очереди: независимой переменной присваиваем значение указателя начала, задаем цикл, до того момента как указатель не будет равен nil; выписываем содержимое звена и указателю задаем значение следующего звена:

S: =Sn;

While s<>nil do begin

Write;

S: =s^. Next; end;

Функция проверки на пустоту очереди выглядит следующим образом:

• Empty: =Sn=SK;
• Функция может принимать два значения. Если начало и конец совпадают, то функция равна правде, и наоборот: не совпадают – лжи.

Процедура вставки:

new;

P^. Next: =nil;

• P^. Elem: =x;
• Sk^. Next: =p;

sk:=p;

создается новое звено, указатель которого равен nil, информационной ячейке придается какое-то значение, и указатель конца передвигается к этому звену.

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

Remove= Sn^. Elem;

• Sn: =Sn^. Next;

Sk

Для того чтобы не было заполнение памяти ненужной информацией, используют процедуру dispose , которая освобождает память.

P: =Sn;

Remove= Sn^. Elem;

• Sn: =Sn^. Next;

Dispose;

Тема №3: деки.

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

nil ,

Uses CRT; {описание переменных}

Type typeelem=Integer;

• connect=^data;

data=Record

elem: typeelem;

• Next: connect;

Pred : connect

End;

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

Для уменьшения процедур можно использовать вспомогательные процедуры:

Культура безопасности как неотъемлемый элемент культуры производства. ...

... Они – элементы реальной деятельности и ее специфичности на каждом конкретной предприятии. И они конкретны для каждого предприятия. Заметим, что культура безопасности и культура производства легко ... координированной деятельности в сфере охраны труда. Высшее руководство является ключевым звеном в обеспечении «культуры безопасности» всей системы управления производством, и именно принципы и действия ...

• Procedure insert1;

{занесение элемента в дек после заданного звена}

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 используется при вставке элемента после заданного звена при условии что это не начало или не конец дека.}

Procedure insert3;

{занесение элемента в дек до заданного звена}

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 используется при вставке элемента до заданного звена при условии что это не начало или не конец дека}

Procedure insert2;

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

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 – вставка элемента в начало или в конец дека}

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

Procedure insertnext;

{занесение элемента x в дек после заданного звена}

var s1, s2, p:connect;

Begin

s1:=sn1; s2:=sn2;

if then insert1

else insert2; end;

• В противоположность первого случая, указателю предыдущего элемента присваиваем значение нового звена, указателю конца так же присваиваем значение нового звена.

Procedure insertpred;

{занесение элемента в дек до заданного звена}

var s1, s2, p:connect;

Begin

s1:=sn1;

s2:=sn2;

if then insert3

else insert2

end;

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

next

Function remove:typeelem;

{ удаление элемента из дека }

Динамические структуры данных: списки

... Списки Обсудим вопрос о том, как в динамической памяти можно создать структуру данных переменного размера. Разберем следующий пример. В процессе ... ReadLn(S); Assign(T, S); Reset(T); MidReal := 0; MidInt := 0; Randomize; NEW(PReal); {Выделение памяти под вещественный массив} {Ввод и ... массивов. В версиях Турбо-Паскаля, работающих под операционной системой MS DOS, под данные одной программы выделяется 64 ...

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}

Если звено первое, то значению функции присваиваем значение первого элемента; если – второе, то – последнего элемента.

Заключение:

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

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

Стековых структур данных, очередей и деков в среде «ТУРБО ПАСКАЛЬ» как тип переменных не существует, поэтому, для наглядности, используют массивы и линейные списки.

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

Приложение

Стек:

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;

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;

Разработка компьютерной игры «Змейка»

... и даже маркетинговые ходы. Целью же моей курсовой работы будет разработка развивающей ловкость игры - "Змейка". компьютерная игра pascal ... этом змейка должна "разбиваться" при столкновении с границей игрового поля и со своим "хвостом". 4. Должна присутствовать ... с помощью процедуры Read, Readln, Write, Writeln оказывается явно недостаточно для разработки диалоговых программ. Поэтому при написании своей ...

writeln;

readln;

for i:=1 to n do

begin

if) mod f=0 then

push);

pop;

end;

writeln;

list;

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;

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;

• 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;

randomize;

init;

for i:=1 to n do

begin

y:=random-random;

push;

end;

list; Writeln;

y:=pop;

pop;

push;

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;

• randomize;

init;

init;

for i:=1 to n do

begin

y:=random-random;

push;

end;

list; Writeln;

f:=pop;

repeat

Карл эдуа рд сага н англ

... представляло собой пластину анодированного алюминия, прикреплённую к космическому зонду Пионер-10. Карл Саган продолжил работу над посланиями. Самым детальным посланием, в разработке которого он ... показано место посадки «Марс Патфайндера» и историческая надпись, цитирующая Сагана на месте «Мемориальной станции Карла Сагана», которая гласит: Unseen Forces 8. Премии и награды Премия достижений ...

y:=pop;

push;

until empty;

push;

repeat

y:=pop;

push;

until empty;

• list;
• Writeln;

• 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;

• 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

else writeln;

while not empty do begin

y:=pop;

push; end;

list;

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+abs);

push);

pop;

end;

push;

for i:=1 to n-1 do

begin

push);

pop;

end;

list;

randomize;

init;

init;

for i:=1 to n-1 do

begin

y:=random-random;

push;

end;

list; Writeln;

f:=1;

for i:=1 to n-1 do

begin

f:=f*abs);

push);

pop;

end;

push;

for i:=1 to n-1 do

begin

push);

pop;

end;

list;

writeln;

randomize;

init;

init;

for i:=1 to n do

begin

y:=random-random;

push;

end;

list; Writeln;

Writeln;

readln;

Классификация текстов по функциональным стилям речи

... жанры можно сопоставить стилям русского языка (редакторский жанр – научный стиль, репортерский жанр – газетный стиль и т.д.) поэтому в данном курсовом ... которых получается несколькими способами (какими именно описано ниже). Главное ... учитывая стили текстов [2]. В веб-приложениях определение стиля упрощает работу врапперам ... (Random Feature Subspacing Ensemble RFSE). One-class SVM. Для каждого жанра ...

for i:=1 to n do

begin

y:=stacktop-f;

push;

pop;

end;

push;

for i:=1 to n do

begin

push);

pop;

end;

list;

randomize;

init;

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

push);

pop;

end;

for i:=1 to n do

begin

push);

pop;

end;

list;

init;

init;

init;

for i:=1 to n do

push;

list; Writeln;

while not emptydo begin

push);

push);

end;

while not or empty) do begin

push);

push);

end;

list;

init;

init;

init;

for i:=1 to n do

push;

list; Writeln;

while not emptydo begin

push);

push);

end;

while not or empty) do

push);

while not or empty) do

push);

list;

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);

while not emptydo

push);

list;

randomize;

init;

init;

init;

init;

for i:=1 to n do

begin

y:=random;

push;

end;

list; Writeln;

while not emptydo begin

push);

while not emptydo begin

if stacktop>=stacktop then

begin push); push); end

else push); end;

push);

while not emptydo

push);

end;

while not emptydo

push);

list; Writeln;

• randomize;

init;

init;

init;

init;

for i:=1 to n do

begin

y:=random;

push;

end;

list; Writeln;

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;

• randomize;

init;

init;

init;

for i:=1 to n do

begin

y:=random;

push;

end;

list; Writeln;

while not emptydo

if stacktopdiv 10=0 then push)

else push);

• list;
• Writeln;

• list;
• Writeln;

• randomize;

init;

push;

y:=0;

for i:=2 to n do begin

y:=y+stacktop;

• push;
• end;

list;

randomize;

init;

init;

init;

for i:=1 to n-1 do

begin

y:=random-random;

push;

end;

list; Writeln;

push);

while not emptydo

if stacktop<=stacktop then begin push); push) end

else push);

push);

while not emptydo

push);

writeln;

list;

randomize;

init;

init;

init;

for i:=1 to n-1 do

begin

y:=random-random;

push;

end;

list; Writeln;

push);

while not emptydo

if stacktop<=stacktop then begin push); push) end

else push);

while not emptydo

push);

push);

writeln;

list;

randomize;

init;

init;

init;

for i:=1 to n-1 do

begin

y:=random-random;

push;

end;

list; Writeln;

push);

while not emptydo

if stacktop<=stacktop then begin push); push) end

else push);

while not emptydo

push);

push);

push);

while not emptydo

if stacktop>=stacktop then begin push); push) end

else push);

push);

while not emptydo

push);

writeln;

Дек:

1. Дан дек из целых чисел, заполненный случайным образом. В начало дека вставить число, вводимое с клавиатуры.
2. Дек состоит из целых чисел. Вставить в этот дек ноль после числа вводимого с клавиатуры.
3. Заполнить дек целыми положительными числами. Вставить в дек сегодняшнее число до элемента, который равен числу вводимому с клавиатуры.
4. Заполнить дек случайным образом целыми числами. Найти максимальный элемент в образовавшемся деке и вставить до и после него ноль.
5. Дан дек, заполненный случайным образом. До после минимального элемента вставить тысячу.
6. В деке, состоящем из целых чисел, вставить перед предыдущим элементом, равным введенному числу с клавиатуры, число равное произведению элемента и предыдущего элемента.
7. Дек заполнен случайными целыми числами. Сортировать данный дек по возрастанию.
8. Заполнить дек случайными целыми числами и отсортировать его по убыванию.
9. Найти сумму всех элементов дека, заполненного целыми числами, и поместить эту сумму в конец дека.
10. Найти сумму всех элементов дека, который состоит из целых чисел, и приписать эту сумму в начало дека.
11. Дек заполнен случайным образом целыми числами. Найти в деке максимальный и минимальный элементы и поменять их местами.
12. Дан дек, заполненный целыми положительными и отрицательными числами. Найти в данном деке отрицательные элементы и удалить их.
13. Удалить четные элементы дека, заполненного случайным образом целыми числами.
14. Удалить нечетные элементы в деке, который заполнен целыми числами.
15. Найти в данном деке, заполненном случайным образом, отрицательные элементы, удалить эти элементы и вставить вместо них модули удаленных.
16. Дек состоит из целых отрицательных и положительных чисел, заданных случайным образом. Найти и записать вместо положительных элементов, равные им по модулю отрицательные числа.
17. Перед отрицательными элементами данного дека, который состоит из целых отрицательных и положительных чисел, вставить их модули.
18. После каждого элемента дека вставить сумму всех элементов дека. Дек состоит из целых чисел.
19. Удалить из дека все двухзначные числа. Дек заполнен случайным образом целыми числами.
20. Дан дек из целых чисел, заданных случайным образом. Оставить в деке только двухзначные числа, все остальные удалить.
21. Удалить из дека нечетные отрицательные числа. Дек заполнен случайным образом целыми числами.
22. Дек заполнен целыми положительными и отрицательными числами. Удалить из дека все положительные четные числа.
23. Дек состоит из целых чисел, заданных случайным образом. Переписать дек в обратном порядке.
24. В деке находятся целые числа. Добавить в дек столько элементов, чтобы он стал в два раза длиннее и симметричным, то есть: первый элемент был равен последнему, второй – предпоследнему и так далее.
25. Дан дек из целых чисел, заданных случайным образом. Если дек содержит четное количество элементов, то добавить в середину дека максимальный элемент; если же дек содержит нечетное количество элементов, то удалить из него средний.
26. Дан дек из целых чисел, заданных случайным образом. Если дек содержит четное количество элементов, то добавить в середину дека минимальный элемент; если же дек содержит нечетное количество элементов, то удалить из него средний.

Очередь:

1. Дана очередь из целых чисел. Удалить из нее все отрицательные элементы.
2. Сравнить модули сумм положительных и отрицательных элементов очереди. Очередь заполнена целыми числами.
3. Добавить в конец очереди сумму модулей всех элементов. Очередь состоит из целых положительных и отрицательных чисел.
4. Очередь заполнена случайным образом целыми числами. Добавить в начало очереди произведение всех элементов.
5. Вычесть из всех элементов очереди число вводимое с клавиатуры.
6. Прибавить ко всем элементам число вводимое с клавиатуры. Очередь заполнена целыми числами.
7. Записать очередь в обратном порядке. Очередь заполняется с клавиатуры.
8. Дана очередь из целых чисел. Удалить из нее числа кратные заданному с клавиатуры числу.
9. Элемент из начала очереди поменять с последним элементом.
10. Дана очередь из целых чисел. Поменять в очереди первый элемент со вторым, третий с четвертым и так далее до конца очереди.
11. В начало очереди поместить элементы с четными номерами, а вконец – с нечетными.
12. Очередь состоит из целых чисел. Поместить в начало очереди четные, а вконец – нечетные элементы.

Основные процедуры:

Стек:

{Реализация стека на основе массива}

Program st;

• Uses Crt;
• Const n=10;
• Type typeelem=Integer;
• stack=Array Of typeelem;
• Var s:stack;
• y:typeelem;
• i: Integer;

• Procedure init;
• Var i: Integer;

Begin

For i:=1 To n Do s:=-1000

End; {init}

Procedure list;

• Var i: Integer;

Begin

Writeln;

i:=1;

While And Do Begin Writeln; Inc End

End; {list}

Procedure push;

• Var i: Integer;

Begin

For i:=n Downto 2 Do s:=s;

s:=x

End; {push}

Function pop:typeelem;

• Var i: Integer;

Begin

pop:=s;

For i:=1 To n-1 Do s:=s;

s:=-1000

End; {pop}

Function stacktop:typeelem;

Begin

stacktop:=s

End; {stacktop}

Function empty: Boolean;

Begin

empty:=false;

• End; {empty}

{–}

Begin {main}

Clrscr;

init;

list; Writeln;

• For i:=1 To 3 Do push;
• Writeln;
• list;

• Writeln);
• y:=stacktop;
• Writeln;
• Writeln;

• Writeln;
• list;
• Writeln;

• For i:=1 To 2 Do Begin y:=pop;
• Writeln End;

• Writeln;
• list;
• Writeln;

• y:=pop;
• Writeln;

• Writeln;
• list;

• Writeln);

Readln

End. {main}

Очередь:

{pеализация очереди на основе лин списка}

Program spisok;

• Uses Crt;
• Type typeelem=Integer;
• 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;

p^.next:=nil;

• sn:=p;
• sk:=p;

• End; {init}

Procedure list;

{распечатка содержимого очереди}

var s:connect;

begin

s:=sn^.next;

• while s<>nil do begin

write;

s:=s^.next; end;

• End; {list}

Function empty: Boolean;

{проверка очереди на пустоту}

Begin

empty:=sn=sk;

• End; {empty}

Procedure insert;

{занесение элемента x в очередь}

var p:connect;

Begin

new;

p^.next:=nil;

• p^.elem:=x;
• sk^.next:=p;

sk:=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;

list; writeln; {распечатка содержимого очереди}

x:=remove; {удаление элемента из очереди}

list; writeln; {распечатка содержимого очереди}

Readln; End.

Дек:

{pеализация дека на основе линейного списка}

Program dek;

• Uses Crt;
• Type typeelem=Integer;
• connect=^data;

data=Record

elem:typeelem;

• next:connect;

pred:connect

End;

Var sn1, sn2, s:connect; x, y:typeelem; i: Integer;

• k:string;
• Procedure init;

{создание дека }

var p:connect;

Begin

new;

p^.next:=nil;

• p^.pred:=nil;
• p^.elem:=x;

sn1:=p;

sn2:=p;

End; {init}

Procedure listnext;

{распечатка содержимого дека в прямом порядке}

var s:connect;

begin

s:=sn1;

while s<>nil do begin

write;

s:=s^.next; end;

write;

End; {list}

Procedure listpred;

{распечатка содержимого дека в обратном порядке}

var s:connect;

begin

s:=sn2;

while s<>nil do begin

write;

s:=s^.pred; end;

write;

End; {list}

Function empty: Boolean;

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

Begin

empty:=sn1=sn2;

• End; {empty}

Procedure insert1;

{занесение элемента x в дек после заданного звена}

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;

Procedure insert3;

{занесение элемента x в дек до заданного звена}

var s1, s2, p:connect;

Begin

s1:=sn1;

s2:=sn2;

while s1^.next^.elem<>y do s1:=s1^.next;

• while s2^.elem<>y do s2:=s2^.pred;

new;

p^.elem:=x;

• p^.next:=s2;
• p^.pred:=s1;
• s2^.pred:=p;
• s1^.next:=p;

end;

Procedure insert2;

{занесение элемента x в дек}

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}

Procedure insertnext;

{занесение элемента x в дек после заданного звена}

var s1, s2, p:connect;

Begin

s1:=sn1;

s2:=sn2;

if then insert1

else insert2

end;

Procedure insertpred;

{занесение элемента x в дек до заданного звена}

var s1, s2, p:connect;

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}

Function remove2:typeelem;

{удаление элемента из конца}

Begin

remove2:=sn2^.elem;

• 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;

• while s2^.pred^.elem<>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;

for i:=2 to 10 do

insert2;

listnext;

writeln;

listpred;

writeln;

insertnext;

• listnext;

writeln;

insertpred;

• listnext;

writeln;

remove1;

listnext;

writeln;

listpred;

writeln;

remove2;

listnext;

writeln;

listpred;

remove;

writeln;

listnext;

writeln;

listpred;

Readln

End.

Литература

[Электронный ресурс]//URL: https://litfac.ru/kursovaya/dinamicheskie-strukturyi-dannyih/

стек дек очередь переменная

1. Информатика и образование, №5 – 1999.
2. Бабушкина И.А., Бушмелева Н.А., Окулов С.М., Черных С.Ю. Конспекты по информатике. – Киров, 1997.
3. Грэхем Р., Кнут Д., Паташник О. Конкретная информатика. – М.: Мир, 1988.
4. Вирт Н., Алгоритм + структура данных = программа.
5. Райнтли, Абстракция и структура данных.
6. Зубов В.С., Справочник программиста. – 1999.