Объяснение структуры данных стека

Учебные заметки: структуры данных и алгоритмы Python

Обзор

Стеки - это популярные линейные структуры данных или, говоря более абстрактно, последовательная коллекция. Со стеком связаны две основные операции; 1) добавление элементов, также известное как push 2) удаление элементов, также известное как pop. Каждая операция может выполняться только в конце последовательности, поэтому операции выполняются по принципу Последний пришел - первый ушел (LIFO). Это показано, что последний элемент, добавленный в стек, будет удален первым.

Название «стопка» происходит от подобия расположения элементов, уложенных друг на друга. Простой способ вспомнить стопки - это представить себе книжную полку, на которой книги сложены одна на другую. Чтобы добавить книгу в стопку, вы должны поместить ее в верхнюю часть стопки, а если вы хотите удалить книгу, вы сначала снимаете верхнюю книгу, пока не дойдете до нужной книги.

Почему существуют стеки?

Стеки чрезвычайно полезны, когда важен порядок действий. Например, подумайте о том, когда вы нажимаете «Отменить» / «Повторить». Выполненные вами действия помещаются в стек, и когда вы выбираете «отменить», последнее действие извлекается из стека, однако количество раз, которое вы можете нажать «Отменить», зависит от размера стека. Таким образом, стеки гарантируют, что предыдущие действия завершены, прежде чем перейти к новому действию.

Преимущества

• Помогает управлять данными в порядке LIFO (Last in First Out)
• Нельзя легко повредить, так как никто не может вставить данные в середину

Недостатки

• Произвольный доступ невозможен

Стеки в Python

Стеки в Python могут быть реализованы несколькими способами. В этой статье я сосредоточусь в первую очередь на использовании структур данных и встроенных модулей Python для реализации нашего стека. В Python реализованы стеки следующими способами:

Список

Python list можно использовать как стек. Вместо метода push() мы просто используем метод append() для добавления новых элементов в верхнюю часть стека. Чтобы удалить элементы в порядке LIFO, мы используем метод pop(), который удаляет последний элемент, добавленный в стек.

# example of list to implement stack
stack = []
stack.append(1)
stack.append(2)
stack.append(3)

print(stack)
>>>> [1, 2, 3]

print(stack.pop())
>>>> 3
print(stack.pop())
>>>> 2
print(stack.pop())
>>>> 1
print(stack)
>>>> []

Внутри список представлен в виде массива; самые большие затраты возникают из-за выхода за пределы текущего размера выделения (потому что все должно перемещаться) или из-за вставки или удаления где-то в самом начале (потому что все после этого должно перемещаться). Если вам нужно добавить / удалить с обоих концов, рассмотрите возможность использования вместо этого collections.deque . - Сложность времени Python

Программисты на Python обычно узнают о list на раннем этапе обучения, поэтому легче всего понять различные методы. Однако по мере увеличения размера списка скорость операций может стать проблемой. Это зависит от того, как элементы в списке хранятся в памяти - элементы списка хранятся рядом друг с другом в непрерывной памяти. Как только стек [в форме списка] превышает блок памяти, который он в настоящее время удерживает, Python выполняет выделение памяти. Именно эта процедура вызывает задержки при попытке append() новых элементов.

collections.deque

Модуль collections также служит удобным способом реализации стеков. Используя класс deque, мы можем преодолеть главную ловушку, очевидную при использовании list - проблему непрерывной разметки памяти.

# example of collections.deque to implement stack
from collections import deque
stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)

print(stack)
>>>> deque([1, 2, 3])

print(stack.pop())
>>>> 3
print(stack.pop())
>>>> 2
print(stack.pop())
>>>> 1
print(stack)
>>>> deque([])

Хотя операции напоминают операции list, внутри deque представлен в виде двусвязного списка (или списка массивов, а не объектов, если быть более точным - для большей эффективности). Каждый элемент хранится в собственном блоке памяти со ссылкой на следующую запись в списке и предыдущую запись. Следовательно, добавить узлы в любой конец списка просто.

Функциональность deque позволяет нам append() или pop() элементов из стека с временной сложностью O (1), однако просмотр элементов в середине стека происходит медленно, а добавление или удаление из середины еще медленнее [в сравнении к списку].

Примечание. Мы редко выполняем индексацию или нарезку стека. Узнать больше о Python Time Complexity

queue.LifoQueue

Следующий вариант - использовать модуль queue, который реализует стеки с классом LifoQueue. Мы используем put() для добавления элементов в стек и get() для удаления элементов.

# example of queue.Lifoqueue to implement stack
# source code https://www.geeksforgeeks.org/stack-in-python/
from queue import LifoQueue
# Initializing a stack
stack = LifoQueue(maxsize = 3)
# qsize() show the number of elements in the stack
print(stack.qsize())
>>>> 0 
# put() function to push element in the stack
stack.put(1)
stack.put(2)
stack.put(3)
print("Full: ", stack.full())
print("Size: ", stack.qsize())
>>>> Full: True
>>>> Size: 3
# get() function to pop element from stack in LIFO order
print(stack.get())
>>>> 3
print(stack.get())
>>>> 2
print(stack.get())
>>>> 1
print("\nEmpty: ", stack.empty())
>>>> Empty: True

Заворачивать

Стеки - это популярные линейные структуры данных, в которых элементы хранятся в порядке «последний пришел - первый ушел» (LIFO). Представление стопки как стопки книг, тарелок или функции отмены (ctrl + z) - простой способ представить себе, как работают стопки. По сути, мы добавляем новый элемент в верхнюю часть стека и удаляем элемент из верхней части стека - эти операции обычно называются push и pop.

Спасибо за чтение!

Если вам понравилась эта статья, свяжитесь со мной, подписавшись на мою БЕСПЛАТНУЮ еженедельную рассылку. Не пропустите мой пост об искусственном интеллекте, машинном обучении и фрилансе.

Статьи по Теме