Рассмотрим реализацию стека с использованием связанного списка. В этой реализации каждый элемент стека представлен объектом класса StackObj, который содержит данные и ссылку на следующий элемент. Сама структура стека реализована в классе Stack.
Класс StackObj
Этот класс представляет собой элемент стека. Он содержит два атрибута:
- data — данные, хранящиеся в элементе стека.
- next — ссылка на следующий объект в стеке.
Конструктор __init__
Конструктор принимает параметр data и инициализирует атрибуты объекта.
Метод __repr__ переопределен для удобного вывода объекта в виде строки.
Класс Stack
Этот класс реализует саму структуру стека. Он содержит атрибут top, который указывает на верхний элемент стека (последний добавленный элемент).
Конструктор __init__
Конструктор инициализирует пустой стек, устанавливая атрибут top в None.
Метод push
Метод push добавляет новый объект в стек. Если стек не пустой, новый объект становится новым верхним элементом, а его next указывает на прежний верхний элемент.
Метод pop
Метод pop удаляет и возвращает верхний элемент стека. Если стек пустой (top равен None), метод возвращает None.
Теперь создадим несколько объектов для стека и протестируем нашу реализацию.
Пояснение работы
- Создание объектов:
Мы создали три объекта StackObj с данными '1', '2' и '3'. Каждый объект при создании имеет атрибут next, равный None. - Добавление объектов в стек (push):
При добавлении первого объекта obj_1 в стек, он становится верхним элементом, так как стек был пуст.
Второй объект obj_2 добавляется, и его next указывает на obj_1, который был верхним.
Третий объект obj_3 добавляется, и его next указывает на obj_2. Теперь obj_3 становится верхним элементом стека. - Извлечение объектов из стека (pop):
При первом вызове метода pop извлекается obj_3, и верхним элементом становится obj_2.
При втором вызове извлекается obj_2, и верхним становится obj_1.
При третьем вызове извлекается obj_1, и стек становится пустым (top равен None).
Вывод:
Данная реализация стека с использованием связанного списка является удобной и эффективной для случаев, когда важно динамическое управление памятью, так как память выделяется по мере добавления новых элементов. Она также позволяет избежать проблем с перераспределением памяти, характерных для стека, реализованного на основе массива.
Если вы интересуетесь программированием, то напоминаю о нашем курсе по основам программирования Python [START].
В нем много анимации, примеров и разборов домашних заданий. Присоединяйтесь! Ссылка: