Share This
Связаться со мной
Крути в низ
Categories
//Реализация стека на Python

Реализация стека на Python

10.04.2021Category : Python

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

Концепции стеков и очередей довольно простые. Стек (англ. stack — стопка) похож на стопку тарелок. Если у вас есть такая стопка, убирать тарелки вы будете, начиная сверху. Таким образом, последняя тарелка, которую вы положили на стопку, будет убрана первой. Вероятно, вы слышали термин LIFO — Last In First Out («последним пришел, первым ушел»).

realizacija steka na python 47ae392 - Реализация стека на Python

А в очередях все наоборот: первый элемент в очереди удаляется тоже первым. Представьте себе очередь в Starbucks. Первый человек в очереди всегда получает свой кофе первым.

Создаем стек на Python

Итак, давайте рассмотрим упрощенный пример задачи, которую вам могут дать на техническом собеседовании. Советуем параллельно с чтением писать этот код в своем редакторе.

 # Реализуйте стек со следующими методами:  # 1. push(item), добавляющий элемент на вершину стека  # 2. pop(), удаляющий самый верхний элемент стека и возвращающий его.  # Если в стеке нет элементов, метод должен выбросить ошибку или вернуть null.  # Каждый метод должен иметь постоянную временную сложность.

Задача начинается со слова «Реализуйте». Это намекает на то, что от вас ожидается создание класса. Если вы не привыкли еще работать с классами, можете считать их чем-то вроде шаблона объекта. При инициации нового объекта класса Stack он будет иметь все свойства и методы, которые мы определим для этого класса.

Начнем с определения класса, а затем добавим метод __init__. Кроме того мы добавим пустые методы pop() и push(). Ключевое слово pass нужно только для того, чтобы Python не ругался на наличие пустых методов.

class Stack:     def __init__():         pass      def pop():         pass      def push():         pass

Отлично, теперь у нас есть класс Stack. Давайте определим метод __init__, который будет устанавливать все свойства стека при инициализации. То есть, при рождении каждого нового стека мы будем наделять его кое-чем. Есть идеи, чем именно?

Стек по сути своей — список (в Python массивы называются списками) с особыми свойствами: вы можете добавлять или удалять только самый недавний элемент. Исходя из этого, мы представим стек как список и назовем его stack. Чтобы определить свойство класса, в Python используется ключевое слово self. Для доступа к этому ключевому слову его нужно передать в качестве аргумента в метод.

def __init__(self):     self.stack = []

Хорошо, теперь давайте перейдем к методу push(). Он тоже будет принимать self в качестве аргумента, чтобы мы могли иметь доступ к только что определенной переменной stack. Кроме того, он будет принимать item — элемент, который мы хотим добавить на вершину стека.

def push(self, item):     pass

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

def push(self, item):     self.stack.append(item)

Метод pop() будет аналогичным. В Python есть метод .pop(), удаляющий последний элемент списка. Очень удобно! Этот метод возвращает удаляемый элемент. Мы будем сохранять этот элемент в переменную removed, а затем возвращать переменную.

def pop(self):     removed = self.stack.pop()     return removed

Но погодите! У нас есть проблема. Что, если в стеке не останется элементов для удаления? К счастью, в условии задачи нам напомнили о такой ситуации:

 # Если в стеке нет элементов, метод должен выбросить ошибку или вернуть null.

Все, что нам нужно сделать, это добавить условное выражение для проверки этого крайнего случая. Для этого перед запуском .pop мы добавим предложение if, проверяющее, не пуст ли стек. Единственный тип null в Python — это None, так что его мы и вернем, если стек все же пуст.

def pop(self):     if len(self.stack) == 0:         return None     removed = self.stack.pop()     return removed 

Вот и все! Повторим:

class Stack:     def __init__(self):         self.stack = []      def push(self, item):         self.stack.append(item)      def pop(self):         if len(self.stack) == 0:             return None         removed = self.stack.pop()         return removed

Есть еще одна вещь, на которую следует обратить внимание. Все наши методы должны иметь постоянную временную сложность — O(1). Это означает, что их работа должна занимать одинаковое время, независимо от длины стека. Если бы нам пришлось, к примеру, перебирать список в цикле, временная сложность была бы O(n), где n — длина списка. Но нам ничего такого делать не пришлось, так что все в порядке.

Проверка нашего стека

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

Как уже было сказано, классы — это своего рода шаблоны объектов. Мы создали шаблон. Теперь давайте проверим его, создав объект. Вы можете это сделать или в оболочке Python, или внизу вашего файла stack.py. Для простоты назовем стек s.

>>> s = Stack()

Теперь давайте протестируем наш прекрасный метод push(), добавив в стек несколько чисел.

>>> s.push(1) >>> s.push(2) >>> s.push(3)

Если мы выведем наш s.stack, мы получим [1, 2, 3]. Отлично. Давайте теперь проверим метод pop().

>>> s.pop()

Если мы теперь выведем s.stack, мы получим [1, 2]. Обратите внимание, что удалился только последний элемент, при этом вернулось значение 3. Но что будет, если мы продолжим удалять элементы? Нам нужно увидеть, вернет ли наш метод None. Для этого мы повторим ту же команду несколько раз, а затем выведем значение return.

>>> s.pop() >>> s.pop() >>> print(s.pop())

Итак, вы реализовали свой первый стек на Python. Можно сказать, изучили свою первую структуру данных.

Бонус: интеграция метода max()

Подобная задача давалась кандидату на интервью в Amazon. Но там запрашивался еще один дополнительный метод:

 # 3. max(), возвращающий максимальное значение в стеке на данный момент.  # Если в стеке нет элементов, метод должен выбросить ошибку или вернуть null.

Чтобы это сработало, нам нужно кое-что изменить в нашем классе Stack. Начнем с __init__. Давайте добавим переменную max для отслеживания максимального значения в стеке. Условие предлагает нам вернуть нулевое значение, если стек пуст. Поэтому мы инициализируем переменную как None.

def __init__(self):     self.stack = []     self.max = None

Круто. Теперь давайте обновим метод push(). Нам нужно проверить два варианта:

  1. Является ли этот элемент первым элементом, добавляемым в стек. В этом случае текущее значение max — None, и нам нужно инициализировать переменную первым добавляемым значением.
  2. Если max уже имеет какое-то значение, нам нужно сравнить его со значением добавляемого элемента и соответственно обновить.

В обоих случаях мы будем устанавливать новое значение max для добавляемого элемента. Это удачный момент для применения однострочного условия с or.

def push(self, item):     self.stack.append(item)     if len(self.stack) == 1 or item > self.max:         self.max = item

А теперь давайте взглянем на pop(). Опять же, нам нужно проверить два варианта:

  1. Является ли удаляемый элемент последним в стеке. Если стек пуст, нужно установить max в None.
  2. Если удаляемый элемент равен значению max, нужно перебрать в цикле список и найти новое значение.

С первым случаем все просто. После вызова .pop() для списка мы проверяем, стала ли длина списка равной нулю.

if len(self.stack) == 0:     self.max = None

Для проверки второго случая мы используем цикл for. Начнем с установки для max значения, которое, как мы знаем, уже есть в стеке, — первого значения. Затем переберем в цикле весь список и сверим каждое значение с первым. Если значение будет больше self.max, будем обновлять self.max новым, большим значением.

elif removed == self.max:     self.max = self.stack[0]     for value in self.stack:         if value > self.max:             self.max = value

И в конце мы будем возвращать значение, которое удалили из стека. Целиком наш метод будет выглядеть так:

def pop(self):     if len(self.stack) == 0:         return None     removed = self.stack.pop()     if len(self.stack) == 0:         self.max = None     elif removed == self.max:         self.max = self.stack[0]         for value in self.stack:             if value > self.max:                 self.max = value     return removed

Наконец, давайте реализуем метод max(). Назначение этого метода — просто возвращать значение определенной нами переменной max. Но в Python мы можем просто получить доступ к этому значению вне определения класса, вызвав s.max. Зачем же нам писать целый метод, чтобы просто вернуть его?

Это пережиток объектно-ориентированного программирования на Java. Традиционно считается best practice делать все переменные приватными. Если бы вы создавали, скажем, радио, вы бы не захотели, чтобы пользователи копались в проводах. Пользователь должен пользоваться регуляторами и кнопками снаружи. В Java вы бы инициализировали поле max ключевым словом private. Затем вы бы написали метод max или get_max(), возвращающий это значение, и это был бы единственный способ доступа к нему.

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

Итак, мы имеем:

class Stack:     def __init__(self):         self.stack = []         self.max = None      def pop(self):         if len(self.stack) == 0:             return None         removed = self.stack.pop()         if len(self.stack) == 0:             self.max = None         elif removed == self.max:             self.max = self.stack[0]             for value in self.stack:                 if value > self.max:                     self.max = value         return removed      def push(self, item):         self.stack.append(item)         if len(self.stack) == 1 or item > self.max:             self.max = item      def get_max(self):         return self.max

Теперь можно протестировать наш код, добавляя и удаляя элементы и проверяя при этом, правильно ли обновляется переменная max.

>>> s = Stack() >>> s.push(1) >>> s.push(2) >>> s.push(3) >>> s.max 3 >>> s.pop() 3 >>> s.max 2

realizacija steka na python 5fce697 - Реализация стека на Python

Хотите больше материалов по Python

Подписывайтесь на нас в Телеграм

Подписаться ×

  • 1 views
  • 0 Comment

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.

Свежие комментарии

    Рубрики

    About Author 01.

    Roman Spiridonov
    Roman Spiridonov

    Привет ! Мне 38 лет, я работаю в области информационных технологий более 4 лет. Тут собрано самое интересное.

    Our Instagram 04.

    Categories 05.

    © Speccy 2020 / All rights reserved

    Связаться со мной
    Close