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 2020 / All rights reserved

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