Структуры данных — стек

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

В этой статье я расскажу о линейных структурах ( стеках ). По сравнению с нелинейными структурами концепции линейных структур относительно легче понять. Некоторыми примерами таких линейных структур являются Stack, Queues, Deques и Lists. Мы рассмотрим каждую из этих структур данных одну за другой. Эти линейные структуры можно рассматривать как имеющие 2 конца. (спереди и сзади | слева и справа | сверху и снизу) Некоторые линейные структуры позволяют вставлять или удалять элементы только с одного конца, в то время как некоторые структуры позволяют это делать с любого конца.

1. Стеки

• Таким образом, стек — это упорядоченный набор элементов, где вставка и удаление элементов происходят на одном конце. Этот конец широко известен как «Вершина». Также конец, противоположный вершине, известен как «Низ».
• Кроме того, новые элементы находятся вверху, а старые — внизу. Поэтому порядок удаления элементов из стека будет обратным порядку добавления элементов в стек.
• Теперь, когда мы хорошо понимаем поведение стека, давайте рассмотрим некоторые важные операции, связанные со структурой данных стека.
• push (элемент) — метод push используется для вставки элемента в верхнюю часть стека.
• pop () — метод pop используется для удаления самого верхнего элемента из стека
• peek () — метод Peek используется для просмотра текущего самого верхнего элемента стека.
• size () — возвращает количество элементов, присутствующих в стеке.
• is_empty () — Этот метод полезен для проверки, пуст стек или нет.
• Обратите внимание, что здесь конец списка считается вершиной стека. (Временная сложность — O(1)) Мы можем рассматривать начало списка как вершину стека, однако это будет не очень эффективно, поскольку временная сложность будет O(n) , когда мы помещаем или извлекаем элементы.
• Когда мы считаем конец списка вершиной стека


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

• Теперь давайте расширим приведенный выше алгоритм, чтобы преобразовать десятичное число в любую систему счисления от 2 до 16.


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

• На первом этапе этой задачи я рассмотрю только один тип скобок, скажем (). Нам нужно проверить, является ли набор скобок сбалансированным или нет. Если сбалансировано, мы должны вернуть true, иначе false.
• ( ) — сбалансированный | ( ( ) ) — сбалансированный | ( ( ( )( ) ) ) — сбалансированный
• ( ( ) не сбалансирован | ( ) ( ) ( — не сбалансирован | ( ( ( ) ) ( ) – не сбалансирован

• ( [ ] ) — сбалансированный | ( ( ) { } ) — сбалансированный | ( ( [ { } [ ] ] ) ) — сбалансированный
• ( ( ) не сбалансирован | ( ) { } ] — не сбалансирован | ( ( { } [ [ ) — не сбалансирован


3. Перевернуть строку с помощью стека



4. Инфикс | Постфиксная и префиксная запись

В информатике нам приходится иметь дело с большим количеством арифметических выражений. Выражение состоит из операторов (+, -, *, / и т. д.), операндов (A, B, c, d, 1, 2,…) и символов, таких как круглые скобки.

• Инфиксная нотация — в этой нотации оператор помещается между операндами. (<операнд> <оператор> <операнд>)
• Если выражение состоит только из одного оператора (например: 2 + 3, 4 * 6), мы можем решить выражение сразу. Однако, если выражение содержит более одного оператора, мы не можем решить его напрямую из-за неоднозначности выражения. Рассмотрим это выражение 1 + 4 * 5. Если мы сначала выполним сложение, мы получим ответ как [ ( 1 + 4 ) * 5 ] = 25, а если мы сначала выполним умножение, мы получим ответ как [1 + (4 * 5) )] = 21. Как видите, в этом обозначении есть некоторая неоднозначность. Поэтому, чтобы решить эту проблему, мы используем нечто, называемое «приоритетом оператора». В соответствии с приоритетом оператора умножение должно выполняться перед сложением. Так что правильный ответ должен быть 21, а не 25.
• По сути, чтобы решить выражение, записанное в инфиксной нотации, мы должны следовать набору правил, а также нам нужно добавить круглые скобки. Таким образом, эта запись может занять больше памяти при решении. Поэтому, чтобы преодолеть эти проблемы, ученые придумали два других обозначения: префикс и постфикс.
• В префиксной записи оператор помещается перед операндами (<оператор><операнд> <операнд>), тогда как в постфиксной записи оператор ставится после операндов. (<операнд> <операнд><оператор>)
• По сравнению с инфиксной записью, две другие записи довольно трудны для чтения и понимания человеком. Однако, поскольку эти две записи не имеют дополнительных символов, таких как скобки, и не содержат никакой двусмысленности, выражения, записанные в этих двух форматах, могут быть легко прочитаны компьютерами.


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

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


• Теперь давайте посмотрим, как мы можем преобразовать выражение в инфиксном формате в постфиксный с помощью Python.