Введение

Некоторые структуры данных универсальны и могут использоваться в широком спектре приложений, другие специализированы и предназначены для решения конкретных задач. Одной из таких специализированных структур, известной своей простотой, но замечательной полезностью, является стек.

Итак, что такое стек? По своей сути стек представляет собой линейную структуру данных, которая следует за LIFO Принцип (Последний пришел — первый ушел). Думайте об этом как о стопке тарелок в кафетерии; вы берете только ту тарелку, которая находится сверху, а при установке новой тарелки она попадает на вершину стопки.

Последний добавленный элемент является первым элементом, который будет удален.

Но почему понимание стека имеет решающее значение? За прошедшие годы стеки нашли свое применение во множестве областей: от управления памятью в ваших любимых языках программирования до функций кнопки «Назад» в веб-браузере. Эта присущая ему простота в сочетании с широкой применимостью делает стек незаменимым инструментом в арсенале разработчика.

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

Фундаментальные понятия структуры данных стека

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

Принцип ЛИФО (последним пришел — первым ушел)

LIFO — это руководящий принцип стека. Это означает, что последний элемент, попавший в стек, первым его покидает. Эта характеристика отличает стеки от других линейных структур данных, таких как очереди.

Примечание: Еще один полезный пример, который поможет вам понять концепцию работы стеков, — это представить, как люди входят и выходят из стеков. лифт – последний человек, вошедший в лифт, выходит первым!

Основные операции

Каждая структура данных определяется операциями, которые она поддерживает. Для стеков эти операции просты, но жизненно важны:

• Push – Добавляет элемент на вершину стека. Если стек полон, эта операция может привести к переполнению стека.

• Поп – Удаляет и возвращает самый верхний элемент стека. Если стек пуст, попытка извлечения может привести к опустошению стека.

• Пик (или топ) – Наблюдает за самым верхним элементом, не удаляя его. Эта операция полезна, когда вы хотите проверить текущий верхний элемент, не изменяя состояние стека.

К настоящему моменту значение стековой структуры данных и ее основополагающих концепций должно быть очевидным. По мере продвижения вперед мы углубимся в его реализации, проливая свет на то, как эти фундаментальные принципы воплощаются в практический код.

Как реализовать стек с нуля в Python

Поняв основополагающие принципы, лежащие в основе стеков, пришло время засучить рукава и углубиться в практическую сторону вещей. Хотя реализация стека проста, к ней можно подойти несколькими способами. В этом разделе мы рассмотрим два основных метода реализации стека — использование массивов и связанных списков.

Реализация стека с использованием массивов

Массивы, будучи смежные ячейки памяти, предлагают интуитивно понятные средства представления стеков. Они обеспечивают сложность времени O(1) для доступа к элементам по индексу, обеспечивая быстрые операции push, pop и peek. Кроме того, массивы могут быть более эффективными с точки зрения использования памяти, поскольку здесь нет дополнительных затрат на указатели, как в связанных списках.

С другой стороны, традиционные массивы имеют фиксированный размер, то есть после инициализации их размер невозможно изменить. Это может привести к переполнение стека если не контролировать. Это можно преодолеть с помощью динамических массивов (например, Python list), который может изменять размер, но эта операция довольно затратна.

Разобравшись со всем этим, давайте приступим к реализации нашего класса стека с использованием массивов в Python. Прежде всего, давайте создадим сам класс с конструктором, принимающим в качестве параметра размер стека:

class Stack: def __init__(self, size): self.size = size self.stack = [None] * size self.top = -1

Как видите, мы сохранили в нашем классе три значения. size желаемый размер стека, stack — это фактический массив, используемый для представления структуры данных стека, а top это индекс последнего элемента в stack массив (верхняя часть стека).

С этого момента мы создадим и объясним по одному методу для каждой базовой операции со стеком. Каждый из этих методов будет содержаться в Stack класс, который мы только что создали.

Давайте начнем с push() метод. Как обсуждалось ранее, операция push добавляет элемент на вершину стека. Прежде всего, мы проверим, осталось ли в стеке место для элемента, который мы хотим добавить. Если стек полон, мы поднимем Stack Overflow исключение. В противном случае мы просто добавим элемент и настроим top и stack соответственно:

def push(self, item): if self.top == self.size - 1: raise Exception("Stack Overflow") self.top += 1 self.stack[self.top] = item

Теперь мы можем определить метод удаления элемента с вершины стека – метод pop() метод. Прежде чем мы попытаемся удалить элемент, нам нужно будет проверить, есть ли какие-либо элементы в стеке, потому что нет смысла пытаться извлечь элемент из пустого стека:

def pop(self): if self.top == -1: raise Exception("Stack Underflow") item = self.stack[self.top] self.top -= 1 return item

Наконец, мы можем определить peek() метод, который просто возвращает значение элемента, который в данный момент находится на вершине стека:

def peek(self): if self.top == -1: raise Exception("Stack is empty") return self.stack[self.top]

Вот и все! Теперь у нас есть класс, который реализует поведение стеков с использованием списков в Python.

Реализация стека с использованием связанных списков

Связанные списки, будучи динамические структуры данных, может легко увеличиваться и уменьшаться, что может быть полезно для реализации стеков. Поскольку связанные списки выделяют память по мере необходимости, стек может динамически увеличиваться и уменьшаться без необходимости явного изменения размера. Еще одним преимуществом использования связанных списков для реализации стеков является то, что операции push и pop требуют лишь простых изменений указателя. Обратной стороной этого является то, что каждый элемент связанного списка имеет дополнительный указатель, потребляющий больше памяти по сравнению с массивами.

Как мы уже обсуждали в «Связанные списки Python» В статье первое, что нам нужно реализовать перед созданием фактического связанного списка, — это класс для одного узла:

class Node: def __init__(self, data): self.data = data self.next = None

Эта реализация хранит только две точки данных — значение, хранящееся в узле (data) и ссылку на следующий узел (next).

Наша серия из трех частей о связанных списках в Python:

Теперь мы можем перейти к самому классу стека. Конструктор будет немного отличаться от предыдущего. Он будет содержать только одну переменную — ссылку на узел на вершине стека:

class Stack: def __init__(self): self.top = None

Как и ожидалось, push() метод добавляет новый элемент (в данном случае узел) на вершину стека:

def push(self, item): node = Node(item) if self.top: node.next = self.top self.top = node

Ассоциация pop() метод проверяет, есть ли в стеке какие-либо элементы, и удаляет самый верхний, если стек не пуст:

def pop(self): if not self.top: raise Exception("Stack Underflow") item = self.top.data self.top = self.top.next return item

Наконец, peek() метод просто считывает значение элемента с вершины стека (если он есть):

def peek(self): if not self.top: raise Exception("Stack is empty") return self.top.data

Примечание: Интерфейс обоих Stack Классы одинаковы – единственная разница – это внутренняя реализация методов класса. Это означает, что вы можете легко переключаться между различными реализациями, не беспокоясь о внутреннем устройстве классов.

Выбор между массивами и связанными списками зависит от конкретных требований и ограничений приложения.

Как реализовать стек, используя встроенные структуры Python

Для многих разработчиков создание стека с нуля, хотя и является образовательным, может оказаться не самым эффективным способом использования стека в реальных приложениях. К счастью, многие популярные языки программирования оснащены встроенными структурами данных и классами, которые естественным образом поддерживают операции со стеком. В этом разделе мы рассмотрим возможности Python в этом отношении.

Python, будучи универсальным и динамичным языком, не имеет специального класса стека. Однако его встроенные структуры данных, особенно списки и класс deque из collections модуль может легко служить стеками.

Использование списков Python в качестве стеков

Списки Python могут довольно эффективно имитировать стек благодаря своей динамической природе и наличию таких методов, как append() и pop().

• Нажмите операцию – Добавить элемент на вершину стека так же просто, как использовать append() Метод:

  stack = []
  stack.append('A')
  stack.append('B')
  

• Поп-операция – Удалить самый верхний элемент можно с помощью pop() метод без аргументов:

  top_element = stack.pop() 

• Операция «Пик» Доступ к вершине без появления всплывающих окон можно выполнить с помощью отрицательной индексации:

  top_element = stack[-1] 

. Deque Класс от Коллекции Модули

Ассоциация deque (сокращение от двойной очереди) — еще один универсальный инструмент для реализации стека. Он оптимизирован для быстрого добавления и извлечения данных с обоих концов, что делает его немного более эффективным для операций со стеком, чем для списков.

• Инициализация:

  from collections import deque
  stack = deque()
  

• Нажмите операцию – Подобно спискам, append() используется метод:

  stack.append('A')
  stack.append('B')
  

• Поп-операция – Как списки, pop() метод выполняет работу:

  top_element = stack.pop() 

• Операция «Пик» – Подход тот же, что и со списками:

  top_element = stack[-1] 

Когда использовать какой?

Хотя и списки, и деки могут использоваться как стеки, если вы в основном используете структуру как стек (с добавлением и извлечением с одного конца), deque может быть немного быстрее благодаря оптимизации. Однако для большинства практических целей и за исключением случаев, когда речь идет о приложениях, критичных к производительности, списков Python должно быть достаточно.

Примечание: В этом разделе рассматриваются встроенные возможности Python для поведения, подобного стеку. Вам не обязательно изобретать велосипед (путем реализации стека с нуля), когда у вас под рукой есть такие мощные инструменты.

Потенциальные проблемы, связанные со стеком, и способы их преодоления

Хотя стеки невероятно универсальны и эффективны, как и любая другая структура данных, они не застрахованы от потенциальных ошибок. Очень важно осознавать эти проблемы при работе со стеками и иметь стратегии для их решения. В этом разделе мы углубимся в некоторые распространенные проблемы, связанные со стеком, и рассмотрим способы их решения.

Переполнение стека

Это происходит, когда предпринимается попытка поместить элемент в стек, емкость которого достигла максимальной. Это особенно актуально в средах, где размер стека фиксирован, например в некоторых сценариях низкоуровневого программирования или рекурсивных вызовах функций.

Если вы используете стеки на основе массивов, рассмотрите возможность перехода на динамические массивы или реализации связанных списков, которые самостоятельно изменяют размер. Еще одним шагом в предотвращении переполнения стека является постоянный мониторинг размера стека, особенно перед операциями отправки, и предоставление четких сообщений об ошибках или подсказок о переполнении стека.

Если переполнение стека происходит из-за чрезмерных рекурсивных вызовов, рассмотрите итеративные решения или увеличьте предел рекурсии, если позволяет среда.

Отсутствие переполнения стека

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

В средах, где это приемлемо, рассмотрите возможность возврата специального значения при извлечении из пустого стека, чтобы указать на недопустимость операции.

Ограничения памяти

В средах с ограниченной памятью даже динамическое изменение размера стеков (например, на основе связанных списков) может привести к исчерпанию памяти, если они станут слишком большими. Поэтому следите за общим использованием памяти приложением и ростом стека. Возможно, ввести мягкое ограничение на размер стека.

Проблемы безопасности потоков

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

• Мьютексы и блокировки – Используйте мьютексы (объекты взаимного исключения) или блокировки, чтобы гарантировать, что только один поток может выполнять операции со стеком в данный момент времени.
• Атомные операции – Используйте атомарные операции, если они поддерживаются средой, для обеспечения согласованности данных во время операций push и pop.
• Локальные для потока стеки – В сценариях, где каждому потоку нужен свой стек, рассмотрите возможность использования локального хранилища потока, чтобы предоставить каждому потоку отдельный экземпляр стека.

Несмотря на то, что стеки действительно эффективны, знание их потенциальных проблем и активное внедрение решений обеспечат надежные и безошибочные приложения. Признание этих ловушек — это половина дела, а другая половина — внедрение передового опыта для их эффективного устранения.

Заключение

Стеки, несмотря на свою кажущуюся простоту, лежат в основе многих фундаментальных операций в мире вычислений. От анализа сложных математических выражений до управления вызовами функций — их полезность широка и важна. Когда мы изучили все тонкости этой структуры данных, стало ясно, что ее сила заключается не только в ее эффективности, но и в ее универсальности.

Однако, как и в случае со всеми инструментами, его эффективность зависит от того, как он используется. Просто убедитесь, что вы хорошо понимаете его принципы, потенциальные ловушки и лучшие практики, чтобы вы могли использовать истинную силу стеков. Независимо от того, реализуете ли вы его с нуля или используете встроенные возможности таких языков, как Python, именно внимательное применение этих структур данных выделит ваши решения среди других.

• SEO-контент и PR-распределение. Получите усиление сегодня.
• PlatoData.Network Вертикальный генеративный ИИ. Расширьте возможности себя. Доступ здесь.
• ПлатонАйСтрим. Интеллект Web3. Расширение знаний. Доступ здесь.
• ПлатонЭСГ. Углерод, чистые технологии, Энергия, Окружающая среда, Солнечная, Управление отходами. Доступ здесь.
• ПлатонЗдоровье. Биотехнологии и клинические исследования. Доступ здесь.
• Источник: https://stackabuse.com/guide-to-stacks-in-python/