Изучение и эффективное применение структур данных и алгоритмов является важной частью хорошего программиста, а также тем, чего я очень боюсь.
Это не то, к чему я когда-либо возвращался со времен колледжа, и если вы не имеете опыта работы в CompSci/IT, скорее всего, вам никогда не приходилось этому учиться.
Изучение основ структур данных и алгоритмов гарантированно сделает вас лучшим программистом и, что более важно, улучшит ваши навыки критического мышления и подход к решению проблем.
В этой статье я представлю введение вместе с примерами кода и, наконец, реализацией вопросов, связанных со стеками, на Python.
Что такое стек?
Вы можете думать о стопке как о стопке тарелок (или как о стопке книг, которые я еще не успел прочитать). Я продолжаю добавлять новые книги в верхнюю часть стопки. Когда я хочу добраться до книги, мне нужно убрать книгу сверху.
- Стек — это тип линейной структуры данных, в которой хранится набор элементов (это могут быть целые числа, символы, логические значения, числа с плавающей запятой и т. д.).
- Элементы добавляются и удаляются с одного и того же конца, который называется «вершиной» стека.
- Он следует правилу LIFO (последним пришел — первым ушел) для добавления и удаления элементов. Это означает, что первый элемент, который будет добавлен в стек, будет последним элементом, который будет удален, а последний добавленный элемент будет удален первым.
- Двумя основными операциями со стеком являются «push» и «pop».
- Операция push вставляет элемент на вершину стека.
- Операция pop удаляет верхний элемент из стека.
Реализация стека в Python
Во-первых, нам нужно определить класс и реализовать некоторые основные методы. Здесь мы создаем класс под названием «Стек» и используем примитивный тип данных Python «список» для хранения элементов нашего стека.
Для реализации операций push и pop мы используем встроенные в python методы append() и pop(). соответственно.
Операция peek полезна для возврата верхнего элемента стека без его удаления. Здесь stack[-1] возвращает последний элемент списка.
Метод size() возвращает размер стека, а метод isEmpty() возвращает True, если стек пуст и False если он содержит хотя бы один элемент.
И вот оно! Структура данных стека в python. Затем мы можем использовать их в классе Stack следующим образом:
Вопросы о стеках
Вот несколько проблем с кодированием, связанных со стеками. Я буду обновлять ответы в ближайшее время.
- Как можно использовать один массив для реализации трех стеков?
- Как бы вы спроектировали стек, в котором, помимо push и pop, есть функция min, возвращающая минимальный элемент? Push, pop и min должны работать за 0(1) раз.
- Учитывая цепочки скобок, определите, сбалансирована ли каждая последовательность скобок.
Решения
Как можно использовать один массив для реализации трех стеков?
Как бы вы спроектировали стек, в котором, помимо push и pop, есть функция min, возвращающая минимальный элемент? Push, pop и min должны работать за 0(1) раз.
Учитывая цепочки скобок, определите, сбалансирована ли каждая последовательность скобок.
