Как реализовать очередь на Python

Очередь из деревянных уточек

Недавно мы показывали, как реализовать стек на 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 (аналогично для котов).

[python_ad_block]

Но люди могут не выбирать вид животного, а просто брать любое, идущее первым в очереди. Если мы захотим вызвать 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 можно написать по-разному. Мы разобьем его на три условия:

  1. Если кошек нет, мы хотим взять собаку. Метод adopt_dog() будет работать, даже если список dogs пуст.
  2. При наличии и кошек, и собак мы будем их сравнивать. Если первая в очереди собака находится в приюте дольше первой в очереди кошки, мы возьмем собаку.
  3. Если собак нет или первая в очереди кошка находится в приюте дольше собаки, мы возьмем кошку.

Все вместе будет выглядеть так:

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 останется единственным животным в приюте. Будем надеяться, ее тоже скоро заберут.

Прокрутить вверх