Читайте также:
|
Каждую реализацию списков можно рассматривать как реализацию стеков, поскольку стеки являются частными случаями списков с операторами, выполняемыми над списками. Надо представить стек в виде однонаправленного списка, т.к. операторы POP и PUSH будут работать только с ячейкой заголовка и первой ячейкой списка.
Для реализации стека можно рационально приспособить массивы. Поскольку вставка и удаление элементов происходит только через вершину стека, зафиксируем «дно» стека в самом низу массива (в ячейке с наибольшим индексом) и позволим стеку расти вверх массива (к ячейке с наименьшим индексом). Схематично такое представление стека показано на рис. 12.
Рис. 12 – Реализация стека на основе массива
Для такой реализации стеков можно определить абстрактный тип STAK следующим образом:
В этой реализации стек состоит из последовательности элементов element[top], element[top+1],… element[maxlenght ]. Если top = maxlenght +1, то стек пустой.
Ниже приведена программная реализация основных операторов, выполняемых над стеками.
Дата добавления: 2015-07-16; просмотров: 129 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Разновидности очередей | | | Итерационный вычислительный процесс |