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

В общее меню

Введение

Основные
инструкции


Структурированные типы данных

Подпрограммы

Рекурсия

Классы

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

Сортировка
Cтеки

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

По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, т.е. действует принцип "последний пришёл — первый ушёл".

Наиболее наглядным примером организации стека служит детская пирамидка, где добавление и снятие колец осуществляется как раз согласно определению стека.

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

Выделим типовые операции над стеком и его элементами:

  • добавление элемента в стек;
  • удаление элемента из стека;
  • проверка, пуст ли стек;
  • просмотр элемента в вершине стека без удаления;
  • очистка стека.

Реализуем эти операции, используя разработанный ранее модуль для однонаправленных списков (см. материал "Динамические структуры данных: списки").


Используя разработанные здесь библиотеки, решим задачу.

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

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


Контрольные вопросы и задания
  1. Какую структуру данных называют стеком?
  2. На базе каких структур может быть организован стек?
  3. Приведите из жизни примеры организации чего-либо по принципу стека.
  4. Используя стек, напечатайте символы данной строки в обратном порядке.

Назад Вперед


Рейтинг ресурсов УралWeb

 

© Шестаков А.П., 2000-2007
Сайт создан в системе uCoz