Стек — первое знакомство

Уважаемые читатели!

У газеты-вкладки “В мир информатики” появился свой электронный адрес: vmi@1september.ru.

Стеком называют структуру данных, в которой реализован принцип “последним пришел — первым вышел” (по-английски — “Last In First Out”, или LIFO).

Как правило, стек программируют как динамическую (меняющуюся во времени не только по составу, но и по размещению в памяти) структуру связанных между собой элементов. Для этого используют так называемые “указатели” — переменные величины, значением которых является адрес байта памяти. Но мы не будем разрабатывать стек с использованием указателей с соответствующим выделением и освобождением памяти, а рассмотрим упрощенную модель стека — в виде обычного, “статического”, одномерного массива, в котором будем хранить, например, целые числа.

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

Чтобы проиллюстрировать принцип LIFO, используем стек-массив, например, из 10 элементов, который будем изображать “вертикально” (рис. 1).

Рис. 1. Первоначальное состояние стека

Попробуем поместить в стек два числа — сначала число –3 (рис. 2), а потом — 15 (рис. 3).

Рис. 2. В стек поместили первое число; значение top равно 1

Рис. 3. В стек поместили второе число; значение top равно 2

Поместим еще два числа, сначала 7, потом 4 (см. рис. 4).

Рис. 4. В стеке четыре числа; значение top равно 4

Теперь об извлечении элементов из стека. Внимание! Нельзя сразу извлечь число 15, так как перед ним находятся еще два числа — 4 и 7. Извлечь можно только элемент, находящийся на вершине стека, — число 4 (именно оно добавлено в стек последним), после чего можно извлечь число 7 (добавленное предпоследним) и т.д. Отсюда и принцип “последним пришел — первым вышел”.

Разработаем вспомогательные алгоритмы, реализующие работу со стеком. Как принято в газете “В мир информатики”, применим в программах школьный алгоритмический язык. Для этого можно использовать систему программирования “КуМир” версии 4.0 для MS-DOS, но я рекомендую новую версию для операционной системы Windows, которую можно загрузить с сайта http://www.niisi.ru/kumir/¹. Система имеет очень приятный интерфейс (см. рис. 5), в котором, поверьте, программирование превращается в удовольствие!

Итак, приступим. Объявим массив m из 10 элементов и переменную top, о которой шла речь чуть выше:

цел nmax; nmax := 10

цел таб m[1:nmax]

цел top; top := 0

Эти объявления (описания) проводятся перед всеми алгоритмами. Тем самым, под­черкивается, что эти величины общие — они не принадлежат ни одному алгоритму, но все алгоритмы могут к ним обращаться².

Рис. 5

Для работы со стеком нам понадобятся четыре вспомогательных алгоритма:

— Поместить — размещение в стеке нового числа num;

— Извлечь — извлечение числа из стека (извлекаемое число является результатом алгоритма-функции);

— Вершина — функция, возвращающая число на вершине стека (само число из стека не извлекается);

— Очистка — заполнение стека-массива нулями.

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

алг Поместить(арг цел num, nmax,

арг рез цел top,

арг рез цел таб m[1:nmax])

Мы же можем оформить его так³:

алг Поместить(арг цел num)

нач цел i

если top < nmax |Только в этом случае

то |можно добавить элемент

|Смещаем все имеющиеся элементы

|вправо на 1 позицию

нц для i от top + 1 до 2 шаг - 1

m[i] := m[i - 1]

кц

|Записываем в стек новое число

m[1] := num

|Увеличиваем значение top

top := top + 1

иначе

вывод нс, "Стек переполнен!"

все

кон

Остальные вспомогательные алгоритмы:

алг цел Извлечь

нач цел i

если top > 0 |Только в этом случае

то |можно извлечь число

|Берем число на вершине стека

|в качестве значения функции

знач := m[1]

|Смещаем остальные имеющиеся элементы

|влево на 1 позицию

нц для i от 1 до top - 1

m[i] := m[i + 1]

кц

|"Удаляем" значение m[top]

m[top] := 0

|Уменьшаем значение top

top := top - 1

иначе

знач := 0

вывод нс, "Стек пуст!"

все

кон

алг цел Вершина

нач

если top > 0

то

знач := m[1]

иначе

вывод нс, "Стек пуст!"

все

кон

алг Очистка

нач цел i

нц для i от 1 до top

m[i] := 0

кц

кон

Протестируем работу нашего стека. Напишем программу для проверки всех вспомогательных алгоритмов:

цел nmax; nmax := 10

цел таб m[1:nmax]

цел top; top := 0

|Главная программа

алг Проверка

нач цел i

|Подготовим стек

Очистка

|Заполним стек случайными числами

|с использованием функции rnd

нц для i от 1 до nmax

Поместить (int(rnd(20)) - 10)

кц

|А теперь попробуем реализовать

|переполнение

Поместить(5)

|Покажем вершину стека

вывод нс, "Число на вершине стека: ",

Вершина

|Извлечем все элементы

нц для i от 1 до nmax

вывод нс, "Число: ", Извлечь

кц

|Попробуем извлечь элемент

|из пустого стека

вывод Извлечь

кон

Чтобы не запутаться с расположением алгоритмов, договоримся о следующем:

1) общие величины размещаются в самом начале;

2) главная программа (основной алгоритм), решающая конкретную задачу, располагается самой первой;

3) остальные (вспомогательные) алгоритмы размещаются ниже главной программы.

В нашем случае алгоритм Проверка расположен раньше, до вспомогательных алгоритмов.

Запустим программу (+ ) и в окне отладки получим следующий результат:

Стек переполнен!

Число на вершине стека: 4

Число: 4

Число: 6

Число: 7

Число: -3

Число: -1

Число: 1

Число: 6

Число: -7

Число: 1

Число: -10

Стек пуст!

0

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

Задание для самостоятельной работы

На языке программирования, который вы изучаете, разработайте программу, в которой:

1) происходит попытка извлечения числа из “пустого” стека;

2) стек полностью заполняется случайными целыми числами;

3) происходит попытка добавления в стек еще одного элемента;

4) выводится число, находящееся на вершине стека;

5) из стека извлекается половина имеющихся в нем чисел;

6) выводится число, находящееся на вершине стека.

---

1 См. статью “КуМир вернулся!” в “Информатике” № 6/2009. — Прим. ред.

2 Видно, что приведены также и операторы присваивания. Заметим, что любая неветвящаяся последовательность описаний величин и команд, располагаемая перед всеми алгоритмами, в новой версии системы “КуМир” называется вступлением. — Прим. ред.

3 С другой стороны, это делает невозможным использование вспомогательного алгоритма применительно к другим массивам. Но в рассматриваемом случае такое оформление конечно же возможно. — Прим. ред.

---

---

От редакции

В статье Н.А. Насырова “Стек — первое знакомство” в этом выпуске при моделировании стека в виде массива предлагается размещать новое число в стеке и извлекать число из него в начале массива. Используемые в статье вспомогательные алгоритмы значительно упрощаются, если эти операции проводить в конце заполненной части массива, а не в его начале.

Естественно, что при таком варианте моделирования изменится вид рис. 2–4, приведенных в статье.

алг Поместить(арг цел num)

нач

? если top < nmax

? ? то

? ? ? top := top + 1

? ? ? m[top] := num

…

алг цел Извлечь

нач

? если top > 0

? ? то

? ? ? знач := m[top]

? ? ? top := top - 1

? …

алг цел Вершина

нач

? если top > 0

? ? то

? ? ? знач := m[top]

? …

— где top — индекс элемента на вершине стека.

---

¹ См. статью “КуМир вернулся!” в “Информатике” № 6/2009. — Прим. ред.

² Видно, что приведены также и операторы присваивания. Заметим, что любая неветвящаяся последовательность описаний величин и команд, располагаемая перед всеми алгоритмами, в новой версии системы “КуМир” называется вступлением. — Прим. ред.

³ С другой стороны, это делает невозможным использование вспомогательного алгоритма применительно к другим массивам. Но в рассматриваемом случае такое оформление конечно же возможно. — Прим. ред.