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

№

вар.

Задача

1

Создать стек из целых чисел. Вычислить произведение нечётных значе-

ний элементов стека. Организовать просмотр данных стека.

2

Создать очередь из вещественных чисел. Определить количество положи-

тельных значений элементов очереди. Организовать просмотр данных очереди.

3

Дано число N (> 0) и набор из N чисел. Создать стек, содержащий исход-

ные числа (последнее число будет вершиной стека), и вывести указатель на его вершину.

4

Создать очередь, информационными полями которого являются: компью- тер и объем его оперативной памяти. Удалить из очереди сведения о компьютере, которые были введены первыми. Организовать просмотр данных очереди и вычислить общий объем памяти компьютеров, запи-

санных в очереди.

5

Дано число D и указатели P₁ и P₂ на начало и конец очереди, содержащей не менее двух элементов. Добавить элемент со значением D в конец очереди и извлечь из очереди первый (начальный) элемент. Вывести значение извлеченного элемента и содержимое очереди. После извлече- ния элемента из очереди освободить память, занимаемую этим элемен-

том.

6

Создать стек из вещественных чисел. Определить максимальный элемент

в стеке. Организовать просмотр данных стека.

7

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

низовать просмотр данных стека.

8

Создать очередь, информационными полями которой являются: телефон и его цена. Удалить из очереди сведения о телефоне, которые были

введены первыми. Организовать просмотр данных очереди.

9

Создать стек, информационными полями которого являются:   название горы и высота. Добавить в стек сведения о новой горе. Организовать

просмотр данных стека и определить среднюю высоту гор.

10

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

№

вар.

Задача

11

Создать очередь, информационными полями которой являются: фамилия

и средний бал студента. Добавить в очередь сведения о новом студенте. Организовать просмотр данных очереди.

12

Создать очередь, информационными полями которой являются: длины катетов прямоугольного треугольника (два вещественных числа). Доба- вить в очередь сведения о новом треугольнике. Организовать просмотр

данных очереди. Определить периметр треугольника в начале очереди.

13

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

на улице «Дерибасовская».

14

Дано число N (> 0) и указатели P₁ и P₂ на начало и конец непустой очере- ди. Извлечь из очереди N начальных элементов и вывести их значения (если очередь содержит менее N элементов, то извлечь все ее элементы). После извлечения элементов из очереди освобождать память, которую

они занимали.

15

Создать очередь из вещественных чисел. Определить минимальный

элемент очереди. Организовать просмотр данных очереди.

16

Создать стек, информационными полями которого являются: наименова- ние товара и его цена. Добавить в стек сведения о новом товаре. Органи-

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

17

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

товаре. Организовать просмотр данных очереди и вычислить общую стоимость товаров с наименованием «Ручка шариковая».

18

Создать стек из целых чисел. Вычислить среднее арифметическое чётных

значений элементов стека. Организовать просмотр данных стека.

19

Создать очередь, информационными полями которой являются: наимено- вание процессора и его тактовая частота и количество ядер. Добавить в очередь сведения о новом процессоре. Организовать просмотр данных очереди и распечатать данные о многоядерных процессорах (количество

ядер больше 1).

20

Создать очередь из целых чисел. Определить количество четных значе-

ний элементов очереди. Организовать просмотр данных очереди.

21

Создать очередь из целых чисел. Определить среднее значение элементов

очереди. Организовать просмотр данных очереди.

22

Создать стек, информационными полями которого являются: книга и её цена. Добавить в стек сведения о новой книге. Организовать просмотр

данных стека и вычислить среднюю цену книг.

23

Создать очередь из целых чисел. Определить количество положительных элементов очереди. Организовать просмотр данных очереди.

№

вар.

Задача

24

Создать очередь, информационными полями которого являются: книга и

её цена. Добавить в очередь сведения о новой книге. Организовать просмотр данных очереди и вычислить среднюю цену книг.

25

Создать очередь из сведений о клиентах банка: фамилии и суммы на счету. Определить количество клиентов банка, у которых сумма на счету

больше 10000 гр. Организовать просмотр данных очереди.

26

Создать стек, информационными полями которого являются: диск и его объем. Добавить в стек сведения о новом диске. Организовать просмотр

данных стека и вычислить диск с максимальным объемом.

27

Создать очередь из целых чисел. Определить количество элементов

очереди меньших 10. Организовать просмотр данных очереди.

28

Создать стек, информационными полями которого являются:   фамилия работника и его оклад. Добавить в стек сведения о новом работника.

Организовать просмотр данных стека и вычислить средний оклад.

29

Создать очередь из вещественных чисел. Определить количество отрица-

тельных чисел очереди. Организовать просмотр данных очереди.

30

Создать стек, информационными полями которого являются: монитор, диагональ и его цена. Добавить в стек сведения о новом мониторе. Орга- низовать просмотр данных стека и определить количество мониторов с

диагональю более 20 дюймов.

№

вар.

Задача

1

Создать стек целочисленных значений, для реализации используя односвязные списки. Реализовать операции добавления (push) и удале- ния (pop) элемента из стека. Добавьте в стек числа 4, 3, 1, 2, 4 и распеча- тайте содержимое стека. Удалите один элемент из стека, и распечатайте

содержимое стека еще раз. Найдите минимальный элемент, принадле- жащий стеку.

2

Создать очередь вещественных значений, для реализации используя односвязные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь числа: -2.2, 2.3, 2.2, 5.1, 6.7 и распечатайте содержимое очереди. Удалите 3 элемента из очереди, затем добавьте в очередь число 1.9 и распечатайте очередь

еще раз. Найдите произведение элементов, принадлежащих очереди.

3

Создать стек строковых значений, для реализации используя односвяз- ные списки. Реализовать операции добавления (push) и удаления (pop)

элемента из стека. Добавьте в стек строки «abc», «fx», «glc», «hi»,

№

вар.

Задача

«gogo» и распечатайте содержимое стека. Удалите один элемент из

стека, затем добавьте строку «the end» и распечатайте содержимое стека еще раз. Найдите количество строк в стеке, состоящих из 2 символов.

4

Создать очередь строковых значений, для реализации используя одно- связные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь строки «one», «two»,

«three», «four» и распечатайте содержимое очереди. Удалите 2 элемента из очереди, затем добавьте в очередь строку «inf» и распечатайте оче- редь еще раз. Найдите суммарную длину строк, принадлежащих очере- ди, кроме первой строки очереди.

5

Создать стек целочисленных значений, для реализации используя

односвязные списки. Реализовать операции добавления (push) и удале- ния (pop) элемента из стека. Добавьте в стек числа 1, 2, 3, 4, 5 и распеча- тайте содержимое стека. Удалите 3 элемента из стека, и распечатайте содержимое стека еще раз. Найдите сумму элементов стека.

6

Создать очередь вещественных значений, для реализации используя односвязные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь числа 2.1, 2.1, 5.3 и распечатайте содержимое очереди. Удалите 1 элемент из

очереди, затем добавьте в очередь число 4.9 и распечатайте очередь еще раз. Найдите сумму элементов очереди.

7

Создать очередь вещественных значений, для реализации используя

односвязные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь числа 2.2, 1.2, 2.0, 5.2 и распечатайте содержимое очереди. Удалите 2 элемента из очереди, затем добавьте в очередь число 2.9 и распечатайте очередь еще раз. Найдите сумму элементов очереди.

8

Создать стек строковых значений, для реализации используя односвяз- ные списки. Реализовать операции добавления (push) и удаления (pop) элемента из стека. Добавьте в стек строки «sdf», «2», «ssd4», «hello» и распечатайте содержимое стека. Удалите 2 элемента из стека, и распеча-

тайте содержимое стека еще раз. Найдите строку минимальной длины, принадлежащую стеку.

9

Создать очередь строковых значений, для реализации используя одно- связные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь строки «one», «two»,

«three», «four» и распечатайте содержимое очереди. Удалите 1 элемент из очереди, затем добавьте в очередь строку «five» и распечатайте очередь еще раз. * Найдите суммарную длину всех строк, принадлежа- щих очереди.

10

Создать  стек   целочисленных  значений,   для  реализации  используя

односвязные списки. Реализовать операции добавления (push) и удале-

№

вар.

Задача

ния (pop) элемента из стека. Добавьте в стек числа -5, 3, -4, 5 и распеча- тайте содержимое стека. Удалите один элемент из стека, добавьте число

10 в стек, и напечатайте содержимое стека еще раз. * Найдите сумму всех положительных элементов, принадлежащих стеку.

11

Создать очередь вещественных значений, для реализации используя

односвязные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь числа 2.2, 3.2, 2.4, -3.2 и распечатайте содержимое очереди. Удалите 1 элемент из очереди, затем добавьте в очередь число 0.04 и распечатайте очередь еще раз. * Найдите сумму чисел по модулю меньших 1, принадлежащих очереди.

12

Создать стек строковых значений, для реализации используя односвяз- ные списки. Реализовать операции добавления (push) и удаления (pop) элемента из стека. Добавьте в стек строки «Students», «of», «the»,

«group», «TE» и распечатайте содержимое стека. Удалите один элемент из стека, и распечатайте содержимое стека еще раз.

*Напечатайте все строки, начинающиеся со строчной буквы «t», при- надлежащие стеку.

13

Создать очередь строковых значений, для реализации используя одно-

связные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь строки «one», «two»,

«three», «four», «five», «six», «seven» и распечатайте содержимое очере- ди. Удалите 1 элемент из очереди, затем добавьте в очередь строку

«eight» и  распечатайте очередь еще раз. *Найдите количество строк начинающихся с букв «s» или «t».

14

Создать стек строковых значений, для реализации используя односвяз- ные списки. Реализовать операции добавления (push) и удаления (pop) элемента из стека. Добавьте в стек строки «abc», «de», «f», «g», «hi»,

«jk» и распечатайте содержимое стека. Удалите один элемент из стека, и распечатайте содержимое стека еще раз. * Найдите количество одно- символьных строк в стеке.

15

Создать очередь строковых значений, для реализации используя одно-

связные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь строки «one», «two»,

«three», «four» и распечатайте содержимое очереди. Удалите 1 элемент из очереди, затем добавьте в очередь строку «five» и распечатайте очередь еще раз. * Найдите суммарную длину строк, принадлежащих очереди.

16

Создать стек целочисленных значений, для реализации используя односвязные списки. Реализовать операции добавления (push) и удале- ния (pop) элемента из стека. Добавьте в стек числа -5, 3, -4, 5 и распеча-

тайте содержимое стека. Удалите один элемент из стека, добавьте в стек

№

вар.

Задача

число 10, и распечатайте стек еще раз. * Найдите сумму всех положи-

тельных элементов, принадлежащих стеку.

17

Создать очередь вещественных значений, для реализации используя односвязные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь числа 46.5, 3.4, 32.4, -3.21 и распечатайте содержимое очереди. Удалите 2 элемента из очереди, затем добавьте в очередь число 5.0 и распечатайте очередь

еще раз. * Найдите сумму элементов, по модулю больших 12, принад- лежащих очереди.

18

Создать стек строковых значений, для реализации используя односвяз-

ные списки. Реализовать операции добавления (push) и удаления (pop) элемента из стека. Добавьте в стек строки «Students», «of», «the»,

«group», «TE», «3» и распечатайте содержимое стека. Удалите один элемент из стека, и распечатайте содержимое стека еще раз. * Напеча- тайте все строки, которые состоят из двух символов из стека.

19

Создать очередь строковых значений, для реализации используя одно- связные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь строки «one», «two»,

«three», «four», «five», «six», «seven» и распечатайте содержимое очере- ди. Удалите 4 элемента из очереди, затем добавьте в очередь строки

«eight», «nine» и распечатайте очередь еще раз.

* Найдите количество строк, состоящих из 4 символов.

20

Создать стек целочисленных значений, для реализации используя односвязные списки. Реализовать операции добавления (push) и удале- ния (pop) элемента из стека. Добавьте в стек числа 1, 4, 2 и распечатайте содержимое стека. Добавьте число 4 в стек, и распечатайте содержимое

стека еще раз. * Найдите количество чисел, больших числа 3, принад- лежащий стеку.

21

Создать очередь вещественных значений, для реализации используя

односвязные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь числа –2.1, 1.3, -1.34, 3.3 и распечатайте содержимое очереди. Удалите 1 элемент из очереди, затем добавьте в очередь число 2.9 и распечатайте очередь еще раз. * Найдите сумму отрицательных элементов очереди.

22

Создать стек строковых значений, для реализации используя односвяз- ные списки. Реализовать операции добавления (push) и удаления (pop) элемента из стека. Добавьте в стек строки «lll», «2», «sdf4», «bye» и распечатайте содержимое стека. Удалите 1 элемент из стека, и распеча-

тайте содержимое стека еще раз. * Найдите строку максимальной длины, принадлежащую стеку.

23

Создать очередь строковых значений, для реализации используя одно-

связные списки. Реализовать операции добавления (enqueue) и удаления

№

вар.

Задача

(dequeue) элемента из очереди. Добавьте в очередь строки «one», «two»,

«three», «four» и распечатайте содержимое очереди. Добавьте в очередь строку «five» и распечатайте очередь еще раз. * Найдите суммарную длину всех строк, принадлежащих очереди, кроме последней строки очереди.

24

Создать стек целочисленных значений, для реализации используя односвязные списки. Реализовать операции добавления (push) и удале- ния (pop) элемента из стека. Добавьте в стек числа 5, 3, 44, 555 и распе- чатайте содержимое стека. Удалите 2 элемента из стека, добавьте числа 20 и 30 в стек, и напечатайте содержимое стека еще раз. * Найдите

количество положительных двухзначных чисел, принадлежащих стеку.

25

Создать очередь вещественных значений, для реализации используя односвязные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь числа -2.2, 5.5, 4.3, -4.5 и распечатайте содержимое очереди. Удалите 1 элемент из

очереди и распечатайте очередь еще раз. * Найдите сумму чисел по модулю больше 4, принадлежащих очереди.

26

Создать стек строковых значений, для реализации используя односвяз-

ные списки. Реализовать операции добавления (push) и удаления (pop) элемента из стека. Добавьте в стек строки «Student», «of», «the»,

«OSAT» и распечатайте содержимое стека. Удалите один элемент из стека, добавьте строку «ONAT» и распечатайте содержимое стека еще раз. * Посчитайте количество строк, состоящих не менее чем из трех

символов, принадлежащих стеку.

27

Создать очередь строковых значений, для реализации используя одно- связные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь строки «one», «two»,

«three», «four», «five», «six», и распечатайте содержимое очереди. Удалите 2 элемента из очереди, затем добавьте в очередь строку «seven» и распечатайте очередь еще раз. * Найдите количество строк начинаю- щихся с букв «f» или «t».

28

Создать стек целочисленных значений, для реализации используя

односвязные списки. Реализовать операции добавления (push) и удале- ния (pop) элемента из стека. Добавьте в стек числа 1, 2, -3, 4 и распеча- тайте содержимое стека. Удалите один элемент из стека, и распечатайте содержимое стека еще раз. * Найдите максимальный элемент, принад-

лежащий стеку.

29

Создать очередь вещественных значений, для реализации используя односвязные списки. Реализовать операции добавления (enqueue) и удаления (dequeue) элемента из очереди. Добавьте в очередь числа -2.0, 2.0, 2.1, -2.1, 3.7 и распечатайте содержимое очереди. Удалите 2 элемен-

та из очереди, затем добавьте в очередь число 1.1 и распечатайте оче-

№

вар.

Задача

редь еще раз. * Найдите произведение положительных элементов,

принадлежащих очереди.

30

Даны две непустые очереди; адреса начала и конца первой равны P₁ и P₂, а второй — P₃ и P₄. Очереди содержат одинаковое количество элементов. Объединить очереди в одну, в которой элементы исходных очередей чередуются (начиная с первого элемента первой очереди). Вывести указатели на начало и конец полученной очереди. Операции

выделения и освобождения памяти не использовать.

№

вар.

Задача

1

Даны две непустые очереди; адреса начала и конца первой равны P₁ и P₂, а второй —    P₃   и P₄.   Элементы   каждой   из очередей    упорядочены по возрастанию (в направлении от начала очереди к концу). Объединить очереди в одну с сохранением упорядоченности элементов. Вывести указатели на начало и конец полученной очереди. Операции выделения

и освобождения   памяти   не использовать,   поля    с    данными    (Data) не изменять.

2

Арифметическое выражение можно представить в обратной польской записи, где знаки операции следуют за операндами (а не ставятся между ними, как в обычной записи выражений). Обратная польская запись не требует скобок. Например, выражению «1 + 2» соответствует запись «1 2

+», выражению «1 + 2 * 3» запись «1 2 3 * +» (вначале умножаются 2 на 3,

а потом 1 складывается с результатом), «(2 + 3) * (3 – 1)» записывается как «2 3 + 3 1 – *». Задается строка – выражение в обратной польской записи (числа и знаки +, –, * разделены пробелами). Используя стек, вычислите значение выражения. Подсказка: нужно последовательно перебрать все числа и знаки из строки, числа нужно заносить в стек, а как

встретится знак операции, вынимать 2 числа из стека, применять к ним текущую операцию, а результат заносить в стек.

3

Дана последовательность скобок вида «(», «)», «[», «]», «{», «}». Пра- вильными скобочными последовательностями называются пустая после- довательность, а также «(P)», «[P]», «{P}», где P – некоторая правильная последовательность. Например «{}()[]» и «{[][()()]}()» – правильные

скобочные последовательности, а «(]», «[()» и «({)}» – неправильные. Определите является ли заданная строка правильным скобочным выраже-

нием. Подсказка: обработайте по очереди все символы входной строки, помещая открывающие скобки в стек, а для закрывающих скобок извле-

№

вар.

Задача

кайте открывающую скобку из стека и проверяйте, соответствуют ли они

друг другу.

4

Реализуйте очередь, используя два стека. Подсказка: стек инвертирует порядок элементов (т.е. если добавить 1 2 3 4 5, вынимая элементы,

получим 5 4 3 2 1), поэтому если элементы пройдут два стека, то восста- новится их исходный порядок. При помещении в очередь помещайте элемент в первый стек, при извлечении элемента из очереди, извлекайте элемент из второго стека, а если при этом второй стек окажется пустым, перенесите все элементы из первого стека во второй (доставайте элемен- ты первого стека, пока они есть, и переносите во второй).

5

Дано число N (> 0) и две непустые очереди; адреса начала и конца первой

равны P₁ и P₂, а второй — P₃ и P₄. Переместить N начальных элементов первой очереди в конец второй очереди. Если первая очередь содержит менее   N элементов,   то переместить   из первой    очереди    во вторую все элементы. Вывести новые адреса начала и конца первой, а затем второй очереди (для пустой очереди дважды вывести nil). Операции выделения и освобождения памяти не использовать.

6

Дан набор из 10 чисел. Создать две очереди: первая должна содержать числа из исходного набора с нечетными номерами (1, 3, …, 9), а вторая — с четными (2, 4, …, 10); порядок чисел в каждой очереди должен совпа- дать с порядком чисел в исходном наборе. Вывести указатели на начало

и конец первой, а затем второй очереди.

7

Дан набор из 10 чисел. Создать две очереди: первая должна содержать все нечетные, а вторая — все четные числа из исходного набора (порядок чисел в каждой очереди должен совпадать с порядком чисел в исходном наборе). Вывести указатели на начало и конец первой, а затем второй

очереди (одна из очередей может оказаться пустой; в этом случае вывести для нее две константы nil).

8

Даны указатели P₁ и P₂ на начало и конец непустой очереди. Извлекать

из очереди   элементы,   пока значение   начального   элемента    очереди не станет четным, и выводить значения извлеченных элементов (если очередь не содержит элементов с четными значениями, то извлечь все ее элементы). Вывести также новые адреса начала и конца очереди (для пустой очереди дважды вывести nil). После извлечения элементов

из очереди освобождать память, которую они занимали.

9

Даны две очереди; адреса начала и конца первой равны P₁ и P₂, а второй – P₃ и P₄ (если очередь является пустой, то соответствующие адреса рав- ны nil). Переместить все элементы первой очереди (в порядке от начала к концу) в конец второй очереди и вывести новые адреса начала и конца второй    очереди.    Операции     выделения     и освобождения     памяти не использовать.

№

вар.

Задача

10

Даны две непустые очереди; адреса начала и конца первой равны P₁ и P₂, а второй – P₃ и P₄. Перемещать элементы из начала первой очереди в конец второй, пока значение   начального элемента   первой очереди не станет четным (если первая очередь не содержит четных элементов, то переместить из первой очереди во вторую все элементы). Вывести новые адреса начала и конца первой, а затем второй очереди (для пустой

очереди дважды вывести nil). Операции выделения и освобождения памяти не использовать.