Вы можете управлять двумя стеками в одном массиве, размещая один в начале
массива, а другой - в конце. Сохраните отдельные счетчики вершин для каждого стека, и сделайте так, чтобы стеки росли друг к другу, как показано на рис. 3.1. Этот
метод позволяет двум стекам увеличиваться, занимая один и тот же массив памя-
ти до тех пор, пока они не столкнутся друг с другом в тот момент, когда массив
полностью заполнится. Рис. 3.1. Два стека в одном массиве
К сожалению, менять размер подобных стеков непросто. Вы должны выделить
массив под новый стек и скопировать все элементы старого массива в новый. Из-
менение размера больших стеков может занимать очень много времени. Данный
способ совсем не подходит для управления несколькими стеками.
Связанные списки предоставляют более гибкий метод формирования несколь-
ких стеков. Чтобы протолкнуть элемент в стек, надо вставить его в начало связан-
ного списка. Чтобы вытолкнуть элемент из стека, следует удалить первый элемент
связанного списка. Поскольку все элементы добавляются и удаляются только в на-
чале списка, для реализации стеков такого типа не нужны метки или двусвязные
списки. Стеки, строящиеся на связанных списках, не требуют сложных схем пере-
распределения памяти, применяющихся в стеках на основе массивов. Следующий
код демонстрирует процедуры Push и Pop, используемые стеком на основе свя-
занных списков.
Основной недостаток стеков, строящихся на связанных списках, состоит в том,
что они требуют дополнительной памяти для хранения указателей ячеек NextCell.
Отдельный стек на основе массива, содержащий N целых чисел, требует всего 2 * N
байт памяти (по 2 байта на целое число). Тот же самый стек, реализованный как
связанный список, потребовал бы дополнительно 4 * N байт памяти для указате-
лей NextCell, что увеличивает затраты памяти, занятой под стек, втрое.
Программа LStack использует несколько стеков, реализованных в виде связан-
ных списков. С помощью этой программы вы можете вставлять и выталкивать эле-
менты из каждого списка.
Главная
Каталог файлов
