На собеседовании вам вполне могут предложить написать код для реализации стека или очереди. Да, на работе вам, вероятно, за всю карьеру не случится этого делать, но задачи для вайтбоардинга отличаются своей нежизненностью. Несмотря на это, такие задачи — отличный способ продемонстрировать, что вы умеете реализовывать классы (т. е. создавать вещи, которые делают то, что вы сказали им делать).
Концепции стеков и очередей довольно простые. Стек (англ. stack — стопка) похож на стопку тарелок. Если у вас есть такая стопка, убирать тарелки вы будете, начиная сверху. Таким образом, последняя тарелка, которую вы положили на стопку, будет убрана первой. Вероятно, вы слышали термин LIFO — Last In First Out («последним пришел, первым ушел»).
А в очередях все наоборот: первый элемент в очереди удаляется тоже первым. Представьте себе очередь в 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(). Нам нужно проверить два варианта:
- Является ли этот элемент первым элементом, добавляемым в стек. В этом случае текущее значение
max—None, и нам нужно инициализировать переменную первым добавляемым значением. - Если
maxуже имеет какое-то значение, нам нужно сравнить его со значением добавляемого элемента и соответственно обновить.
В обоих случаях мы будем устанавливать новое значение max для добавляемого элемента. Это удачный момент для применения однострочного условия с or.
def push(self, item):
self.stack.append(item)
if len(self.stack) == 1 or item > self.max:
self.max = item
А теперь давайте взглянем на pop(). Опять же, нам нужно проверить два варианта:
- Является ли удаляемый элемент последним в стеке. Если стек пуст, нужно установить
maxвNone. - Если удаляемый элемент равен значению
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
