Составители:
41
1.2.9. Стек
Стек – это структура данных, в которой новый элемент всегда запи-
сывается в ее начало (вершину) и очередной читаемый элемент также
всегда выбирается из ее начала. Здесь используется принцип «после-
дним пришел – первым вышел» (LIFO: Last Input – First Output).
Стек можно реализовывать как статическую структуру данных в виде
одномерного массива, а можно как динамическую структуру – в виде
линейного списка (рис. 8).
При реализации стека в виде статического массива необходимо ре-
зервировать массив, длина которого равна максимально возможной глу-
бине стека, что приводит к неэффективному использованию памяти.
Однако работать с такой реализацией проще и быстрее.
При такой реализации дно стека будет располагаться в первом эле-
менте массива, а рост стека будет осуществляться в сторону увеличе-
ния индексов. Одновременно необходимо отдельно хранить значение
индекса элемента массива, являющегося вершиной стека.
Можно обойтись без отдельного хранения индекса, если в качестве
вершины стека всегда использовать первый элемент массива, но в этом
случае, при записи или чтении из стека, необходимо будет осуществ-
лять сдвиг всех остальных элементов, что приводит к дополнительным
затратам вычислительных ресурсов.
Вершина
…
Дно
Запись
Чтение
i
Дно Вершина…
1 i+1i ……
nil
Дно
…
…
Указатель
на вершину стека
Стек
Динамическая реализация
Статическая реализация
Чтение Запись
Чтение
Запись
Вершина
Рис. 8. Стек и его организация
Страницы
- « первая
- ‹ предыдущая
- …
- 39
- 40
- 41
- 42
- 43
- …
- следующая ›
- последняя »
