Лабораторная работа № 4

Стек и очередь как динамические структуры данных

Линейные списки широко используются для представления таких структур данных, как стеки и очереди.

Стек – структура данных, в которой удалить можно только тот элемент, который был добавлен последним. Коротко этот принцип формулируется так: «последним пришел – первым ушел» или по-английски «last in – first out» (LIFO). Примеры стеков: детская пирамидка, стопка книг или магазин автоматического оружия.

Рис. 4.1. Стопка книг – пример стека

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

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

Рис. 4.2. Представление стека линейным списком

Операции добавления и удаления производятся в голове списка. У пустого стека указатель на голову равен nil (0). Если в стек добавить несколько элементов, то извлекаться они будут в обратном порядке. Операции добавления и удаления элементов из начала линейного списка были рассмотрены на предыдущих лабораторных работах.

Более простой способ моделирования стека ограниченного размера – массив a [0..n-1]. Для стека требуется хранить номер элемента, стоящего после головы стека h (одновременно он определяет и количество элементов стека).

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

НЕ нашли? Не то? Что вы ищете?

…

h=4

8

…

5

2

2

1

1

0

Рис. 4.3. Представление стека массивом

При добавлении элемента в голову стека записываем значение и увеличиваем указатель h:

Язык Pascal

Язык С++

a[h]:=k;

h:=h+1;

a[h++]=k;

Графически процесс добавления в стек числа k, равного 9, можно изобразить так:

…

h=4

8

3

5

2

2

1

1

0

…

9

h=4

8

3

5

2

2

1

1

0

…

h=5

9

4

8

3

5

2

2

1

1

0

Рис. 4.4. Добавление элемента в массив

Для извлечения элемента из головы стека требуется обратная операция:

Язык Pascal

Язык С++

h:=h-1;

k:=a[h];

k=a[--h];

Для пустого стека указатель на голову h равен 0. Затем при добавлении и удалении элементов из стека указатель на голову будет перемещаться по массиву, в то время как конец (хвост, дно) стека всегда будет находиться в нулевом элементе массива. Для вывода всего стека на экран необходимо вывести все элементы массива от элемента с номером h-1 до элемента с номером 0.

Очередь – структура данных, в которой удалить можно только тот элемент, который был добавлен первым. Краткая формулировка этого принципа: «первым пришел – первым ушел» или по-английски «first in – first out» (FIFO). Для реализации очереди используется линейный список с двумя указателями: на голову h (начало) и хвост t (конец).

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

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

Более простой способ моделирования очереди ограниченного размера – массив A[0..N-1]. Для очереди требуются – указатели на голову и хвост h и t.

При добавлении элемента в хвост очереди записываем значение и увеличиваем указатель t:

A[t]:=k;

t:=(t+1) mod N;

t
 
Например, при добавлении в очередь, содержащую 0, 1 и 2, числа k = 3 получаем:

 


0

1

2

3

A:

k
 
 

Удаление из головы очереди:

k:=A[h];

h:=(h+1) mod N;

Например, при удалении из полученной выше очереди числа 0 получим:

h

t

0

1

2

3

A:

Операции по модулю N используются для того, чтобы за элементом N – 1 шел элемент 0.

Задания для лабораторной работы № 4:

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

1) Дано выражение, содержащее скобки трех типов (круглые, квадратные и фигурные). Написать программу, которая проверяет, является ли заданное выражение правильным. Правильным считается выражение, в котором закрыты все открывающиеся скобки, причем скобка, открытая позже, закрывается раньше, и отсутствуют «лишние» закрывающиеся скобки. Например, последовательности

    ({} – неправильная; [ { } ( [ ] ) ] – правильная; [ ( ] ) – неправильная; ( ) ] } – неправильная.

2) Дано выражение в постфиксной форме (обратной польской записи): сначала указаны числа, затем знаки операций. Вычислить его значение. Например:

    6 2 + = 6 + 2 = * 4 + – = 7 – ( 3 * 5 + 4) = – 12

3) Карту, определяющую прямоугольную область моря, представим матрицей с целыми элементами (0 – море, 1 - суша). Островом будем считать множество граничащих по стороне единичных клеток. Рассчитайте количество островов на карте. Найдите площадь самого большого острова. Например, карта

0

1

1

1

0

0

1

0

0

0

1

0

1

1

0

0

1

1

1

0

0

0

0

0

0

0

0

0

1

0

0

0

1

1

1

содержит 4 острова, площадь самого большого равна 7.

4) Даны п кругов различного радиуса. Из них собирают пирамиду, складывая один на другой так, чтобы центры кругов оказались друг над другом. Сколько и какие круги будет видно, если смотреть на такую пирамиду сверху? Например, для кругов с радиусами 6, 2, 1, 5, 3, 4 сверху будет видно 3 круга с радиусами 6, 5 и 4.

5) Лабиринт представляет собой прямоугольную таблицу M x N, в каждой клетке которой может быть препятствие # или проход. Необходимо найти выход из лабиринта от заданной точки до его границ. Например, для приведенного ниже лабиринта (1 показывает точку, из которой следует искать выход) :

#

#

#

#

#

#

#

#

#

1

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

1

2

#

#

#

3

#

#

#

5

4

#

#

6

#

#

#

выход будет выглядеть следующим образом:

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

o для строки abccdeef исходной является строка abdf;

o для строки adccrrrrdf исходной является строка af.

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

Варианты:

1. 6) Последовательность Хэмминга образуют натуральные числа, не имеющие других простых делителей, кроме 2, 3 и 5. Найти первые N элементов этой последовательности. Например, первые 10 элементов такой последовательности будут числа 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.

2. 7) Карту, определяющую прямоугольную область моря, представим матрицей с целыми элементами (0 – море, 1 - суша). Островом будем считать множество граничащих по стороне единичных клеток. Рассчитайте количество островов на карте. Найдите площадь самого большого острова. Например, карта

0

1

1

1

0

0

1

0

0

0

1

0

1

1

0

0

1

1

1

0

0

0

0

0

0

0

0

0

1

0

0

0

1

1

1

содержит 4 острова, площадь самого большого равна 7

3, 8) Последовательность Хэмминга образуют натуральные числа, не имеющие других простых делителей, кроме 2, 3 и 5. Найти сумму первых N элементов этой последовательности. Например, первые 10 элементов такой последовательности будут числа 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.

9) Лабиринт представляет собой прямоугольную таблицу M x N, в каждой клетке которой может быть препятствие # или проход. Необходимо найти выход из лабиринта от заданной точки до его границ. Например, для приведенного ниже лабиринта (1 показывает точку, из которой следует искать выход) :

#

#

#

#

#

#

#

#

#

1

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

#

1

2

#

#

#

3

#

#

#

5

4

#

#

6

#

#

#

выход будет выглядеть следующим образом:

5) 10) Последовательность Хэмминга образуют натуральные числа, не имеющие других простых делителей, кроме 2, 3 и 5. Найти первый элемент, больший данного числа N , а также номер этого элемента в последовательности. Например, первые 10 элементов такой последовательности будут числа 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.