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

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

12.04.2021Category : Python

kak realizovat ochered na python 196be2a - Как реализовать очередь на 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, всем спасибо, все свободны!

Ну ладно, ладно… Давайте сделаем кое-что посложнее.

Задача на создание очереди: приют для животных

kak realizovat ochered na python d780900 - Как реализовать очередь на 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 можно написать по-разному. Мы разобьем его на три условия:

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

kak realizovat ochered na python 5f70421 - Как реализовать очередь на Python

Хотите больше книг по Python

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

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

  • 0 views
  • 0 Comment

Leave a Reply

Ваш адрес email не будет опубликован.

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

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

    Рубрики

    About Author 01.

    blank
    Roman Spiridonov

    Моя специальность - Back-end Developer, Software Engineer Python. Мне 39 лет, я работаю в области информационных технологий более 5 лет. Опыт программирования на Python более 3 лет. На Django более 2 лет.

    Categories 05.

    © Speccy 2022 / All rights reserved

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