Недавно мы показывали, как реализовать стек на Python. Наш код выглядел следующим образом:
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
В книге «Cracking the Coding Interview» стеки реализуются на Java как списки узлов (Node List), а не как массивы (Array). Для этого есть свои причины. Мы решили придерживаться максимальной простоты и для реализации на Python использовали списки.
Чтобы создать очередь, мы изменим наш класс Stack, который создали в прошлый раз. Очереди на самом деле очень похожи на стеки. Но стеки это LIFO (Last In First Out — «Последним пришел, первым ушел»), а очереди, наоборот, — FIFO (First In First Out — «Первым пришел, первым ушел»).
В нашем классе Stack мы добавляли новые элементы всегда в конец списка. Затем, когда при помощи pop() удаляли элемент из списка, это тоже всегда был последний элемент.
Представьте, что начало списка — это голова очереди. Мы продолжаем добавлять элементы в ее хвост, но удаляем с головы. Метод списков pop() в Python может принимать один аргумент — индекс элемента, который нужно удалить. Так что мы можем просто передать в качестве аргумента 0 и таким образом удалять первый элемент списка.
removed = self.stack.pop(0)
Все остальное в нашем классе сохраняется без изменений, разве что переименуем еще переменную stack (теперь она будет queue):
class Queue:
def __init__(self):
self.queue = []
def push(self, item):
self.queue.append(item)
def pop(self):
if len(self.queue) == 0:
return None
removed = self.queue.pop(0)
return removed
Вот и все! Мы разобрали, как создать очередь в Python, всем спасибо, все свободны!
Ну ладно, ладно… Давайте сделаем кое-что посложнее.
Задача на создание очереди: приют для животных
Давайте разберем задачу, которая предполагает создание очереди, но с некоторыми ограничениями.
# В приюте для животных содержатся кошки и собаки. # Люди, желающие взять животное, должны брать # в первую очередь тех, которые содержатся # в приюте дольше всего. # Человек может выбрать, хочет он кошку или собаку. # В результате он получит «старожила» выбранного вида. # Выбирать между кошками и собаками не обязательно: # можно просто взять любое животное, # которое стоит первым в «очереди». # Создайте структуры данных для поддержки этой системы # и реализуйте следующие методы: # addAnimal(), adoptAny(), adoptDog(), adoptCat()
Итак, давайте создадим скелет нашего класса, основываясь на полученной информации. Чтобы наш код соответствовал питоновскому соглашению о нейминге, мы изменим имена переменных с camelCase на snake_case. Также сразу добавим везде ключевое слово self в качестве параметра (просто чтобы не забыть).
class AnimalShelter:
__init__(self):
pass
def add_animal(self):
pass
def adopt_any(self):
pass
def adopt_dog(self):
pass
def adopt_cat(self):
pass
Как обычно, начинаем с метода __init__(). Давайте подумаем, как нам представить каждое животное? А как — очередь животных?
Что касается животных, мы можем создать класс Animal, хранящий сведения о животном, а затем создать отдельные классы Dog и Cat, наследующие эти свойства. Но поскольку эта статья для начинающих, а новички могут еще «плавать» в объектно-ориентированном программировании, мы просто представим каждое животное при помощи словаря. Например:
{
"name": "Emmy",
"type": "dog"
}
Давайте поразмыслим над тем, как нам реализовать очередь в приюте. Мы можем использовать один список и для кошек, и для собак. Но в этом случае, если мы захотим вызвать adopt_dog() или adopt_cat(), нам придется перебирать в цикле весь список, пока не найдем животное нужного вида. Потенциально время работы такого метода будет O(N). Речь идет о случае, когда мы вызываем adopt_dog(), а единственная собака в общем списке идет последней или в списке вообще нет собак.
Однако мы можем разделить очереди собак и кошек. Тогда, чтобы взять собаку, нам нужно будет применить метод pop() к очереди dogs (аналогично для котов).
Но люди могут не выбирать вид животного, а просто брать любое, идущее первым в очереди. Если мы захотим вызвать adopt_any(), нам нужно будет как-то выбрать самое первое животное по обоим спискам. Для этого мы можем отслеживать порядок добавления всех животных и для каждого из них добавить в словаре поле с порядковым номером. Выглядеть это будет так:
{
"name": "Emmy",
"type": "dog",
"order": 1
}
При написании метода __init__() нам нужно инициализировать все необходимые переменные: список, представляющий очередь собак, список, представляющий очередь кошек, и общий порядковый номер, который в начале мы устанавливаем в нуль.
__init__(self):
self.dogs = []
self.cats = []
self.order = 0
Теперь давайте добавим в наш приют какое-нибудь животное. Предположим, что мы знаем кличку животного (name) и его вид (остановимся на kind, потому что слово type — ключевое в Python). Это будут параметры метода. Мы конвертируем kind в нижний регистр во избежание ошибок, вызванных опечатками.
def add_animal(self, name, kind):
kind = kind.lower()
Теперь давайте создадим словарь animal, используя эту информацию. Нам также нужно будет добавить свойство order, а затем увеличить общий порядковый номер на 1. Мы сделаем это до создания животного, таким образом первое животное будет иметь номер 1. Если вы хотите начать с нуля, передвиньте эту строчку ниже объекта animal.
ef add_animal(self, name, kind):
kind = kind.lower()
self.order += 1;
animal = {
"name": name,
"type": kind,
"order": self.order
}
Далее нам нужно решить, к кошкам или собакам мы хотим добавить новое животное (списки cats и dogs). Нам поможет простое if-предложение. В случае, если input не соответствует ни одной из двух опций, мы выведем сообщение об ошибке.
def add_animal(self, name, kind):
kind = kind.lower()
self.order += 1;
animal = {
"name": name,
"type": kind,
"order": self.order
}
if kind == "cat":
self.cats.append(animal)
elif kind == "dog":
self.dogs.append(animal)
else:
print("Invalid animal type entered. Animals must be cat or dog.")
Ладно, теперь давайте возьмем из приюта собаку. Метод adopt_dog() просто возвращает первую собаку из очереди dogs. Мы можем удалить элемент из списка и одновременно вернуть его, как показано ниже. Если очередь пуста, мы вернем None.
def adopt_dog(self):
if len(self.dogs) == 0:
return None
else:
return self.dogs.pop(0)
Круто. Теперь давайте попробуем взять кошку. Кажется, что тут все будет аналогично, только работать будем с очередью cats. Вероятно, вы уже приготовились скопировать код предыдущего метода, но притормозите. Каждый раз, когда вы хотите сделать копипаст чего-либо, есть вероятность, что можно написать более элегантный код, создав более общий метод. Это мы и сделаем. Мы изменим только что написанный метод, чтобы он работал и для adopt_cat, и для adopt_dog.
Начнем с того, что переименуем наш метод в __adopt_animal(). Помните, в статье о создании стека мы говорили, что добавление двойного символа подчеркивания перед именем переменной делает ее приватной? Эта концепция называется «инкапсуляция». То же самое можно делать и с методами, чтобы спрятать те из них, которые вы хотите оставить исключительно для внутреннего использования.
Метод __adopt_animal() будет принимать, кроме self, список животных, с которыми мы хотим работать. И вместо того чтобы осуществлять операции над списком dogs, мы перейдем на новый параметр — animal_list.
def __adopt_animal(self, animal_list):
if len(animal_list) == 0:
return None
else:
return animal_list.pop(0)
Отлично, теперь у нас есть более общая функция. Давайте создадим методы adopt_dog и adopt_cat. В каждом из них мы будем просто вызывать метод __adopt_animal и передавать ему соответственно список собак или кошек.
def adopt_dog(self):
return self.__adopt_animal(self.dogs)
def adopt_cat(self):
return self.__adopt_animal(self.cats)
Пришла пора метода adopt_any(). В этом методе нам нужно вернуть любое животное, находящееся в приюте дольше всех (т. е. не важно, будет это кошка или собака). Мы знаем, что собака-старожил будет идти первой в очереди dogs, а кошка-старожилка — в очереди cats. Нам нужно лишь сравнить их друг с другом. Предложение if можно написать по-разному. Мы разобьем его на три условия:
- Если кошек нет, мы хотим взять собаку. Метод
adopt_dog()будет работать, даже если список dogs пуст. - При наличии и кошек, и собак мы будем их сравнивать. Если первая в очереди собака находится в приюте дольше первой в очереди кошки, мы возьмем собаку.
- Если собак нет или первая в очереди кошка находится в приюте дольше собаки, мы возьмем кошку.
Все вместе будет выглядеть так:
def adopt_any(self):
if len(self.cats) == 0:
return self.adopt_dog()
elif len(self.dogs) > 0 and self.cats[0]["order"] > self.dogs[0]["order"]:
return self.adopt_dog()
else:
return self.adopt_cat()
Это все методы, которые нужны нам для создания класса AnimalShelter. Пожалуй, стоит поменять их местами, чтобы __adopt_animal() был определен до того, как будет вызываться в adopt_cat() и adopt_dog(), а метод adopt_any() пускай идет последним.
class AnimalShelter:
def __init__(self):
self.dogs = []
self.cats = []
self.order = 0
def add_animal(self, name, kind):
kind = kind.lower()
self.order += 1;
animal = {
"name": name,
"type": kind,
"order": self.order
}
if kind == "cat":
self.cats.append(animal)
elif kind == "dog":
self.dogs.append(animal)
else:
print("Invalid animal type entered. Animals must be cat or dog.")
def __adopt_animal(self, animal_list):
if len(animal_list) == 0:
return None
else:
return animal_list.pop(0)
def adopt_dog(self):
return self.__adopt_animal(self.dogs)
def adopt_cat(self):
return self.__adopt_animal(self.cats)
def adopt_any(self):
if len(self.cats) == 0:
return self.adopt_dog()
elif len(self.dogs) > 0 and self.cats[0]["order"] > self.dogs[0]["order"]:
return self.adopt_dog()
else:
return self.adopt_cat()
Тестируем класс
Давайте протестируем написанный нами класс. Начнем с создания объекта AnimalShelter. это можно сделать под вашим кодом или же в оболочке python в консоли. Для краткости назовем объект a.
a = AnimalShelter()
Затем добавим в него несколько животных. Помните, что наш метод принимает два аргумента — имя и вид животного.
a.add_animal("Pizzapie", "cat")
a.add_animal("Emmy", "Dog")
a.add_animal("Sushi", "Cat")
a.add_animal("Charmander", "Dog")
print(a.cats, a.dogs)
Это даст нам два отдельных списка кошек и собак. Обратите внимание, что порядковый номер каждого животного (order) инкрементируется автоматически, так что каждое животное имеет уникальный индекс.
Теперь давайте возьмем из приюта каких-нибудь животных.
a.adopt_cat() a.adopt_dog() a.adopt_any() print(a.cats, a.dogs)
Первое животное, которое будет забрано, — кошка Pizzapie. Затем заберут собаку Emmy. Когда мы запустим adopt_any(), выбор будет делаться между Sushi и Charmander. Поскольку Sushi добавили первой, заберут именно ее. Charmander останется единственным животным в приюте. Будем надеяться, ее тоже скоро заберут.
