|
Реализация стека на Python и C++Курс по структурам данных: https://stepik.org/a/134212 На этом занятии мы реализуем стек на языках Python и C++. Начнем с языка Python. Довольно часто я вижу, как стек делают с использованием списка, то есть, динамического массива: stack = [] stack.append(1) stack.append(2) value = stack.pop() Однако такая реализация будет не самым лучшим вариантом, так как добавление элементов в конец динамического массива может потребовать создания его новой копии, если физического размера текущего массива недостаточно. Конечно, если в стеке предполагается хранить максимум несколько десятков элементов, то динамический массив вполне нормальный выбор. На общую скорость программы это не сильно повлияет. Но если в стеке могут содержаться сотни и тысячи элементов, то лучшим вариантом будет использование специального объекта deque (очереди) из модуля collection, о котором мы уже говорили на предыдущих занятиях: from collections import deque Я напомню, что объект deque основан на двухсвязных списках, то есть, каждый элемент хранит ссылку на следующий элемент и предыдущий элементы. В результате, операции добавления и удаления новых элементов в начало или конец очереди всегда выполняется за одно и то же число операций O(1). Использовать очередь в качестве стека очень просто. Вначале создается объект класса deque: stack = deque() или же с некоторым начальным набором данных: stack = deque([1, 2, 3]) А, затем, с помощью метода append() добавляется новый элемент в конец очереди (вершину стека): stack.append(4) stack.append(5) Для удаления последнего элемента (с вершины стека) используется метод pop(): print(stack.pop()) print(stack.pop()) print(stack.pop()) Как видите, использовать стек в своих программах на языке Python достаточно просто. И предпочтительная его реализация – с помощью объекта очереди deque. Отмечу, что в Python есть еще один объект очереди LifoQueue, который совпадает со своим поведением со структурой стека (добавление и удаление элементов с конца очереди): from queue import LifoQueue Использовать этот объект следует при многопоточном программировании. Но это уже выходит за рамки курса, поэтому подробнее о классе LifoQueue можно почитать в документации по Python. Реализация стека на С++Теперь посмотрим, как реализуется стек на языке С++. В стандартной библиотеке шаблонов STL уже имеется объект, отвечающий за стек. Чтобы им воспользоваться, достаточно подключить библиотеку с именем stack: #include <stack>И, затем, в программе создать объект класса stack следующим образом: int main() { using namespace std; stack<int> st; return 0; } Обратите внимание, после класса stack мы должны в угловых скобках указать тип данных, который будет храниться в объектах стека. Для простоты я указала тип int – целые числа. Затем, через объект st мы можем вызывать различные методы стека. Их совсем немного и они очевидны. Для добавления нового элемента в начало стека используется метод push(), например: st.push(1); st.push(2); st.push(3); Если нужно прочитать значение самого верхнего элемента, используется метод top(): cout << st.top() << endl; Для удаления верхнего элемента применяется метод pop(): st.pop(); cout << st.top() << endl; Или же мы можем в цикле выполнять удаления элементов, пока стек не станет пустым: while (!st.empty()) { cout << st.top() << endl; st.pop(); } Как видите, все достаточно просто. Однако, на самом деле, объект stack в стандартной библиотеке языка С++ - это, так называемый, адаптер, то есть надстройка над другой коллекцией данных. По умолчанию – над очередью: #include <deque>Но при желании можно указать другие коллекции, например, динамический список: #include <vector>и создать объект: stack<int, vector<int>> st; или двухсвязный список: #include <list> stack<int, list<int>> st; Однако использование очереди deque является предпочтительным выбором. Именно поэтому данная коллекция используется по умолчанию. Курс по структурам данных: https://stepik.org/a/134212 Видео по теме |
