I. Очередь

В программировании существует потребность не только в изученных нами коллекциях. Одна из таких очередь. Она реализует подход к хранению данных по принципу «Первый вошёл – первый ушел».

Реализуйте класс Queue, который не имеет параметров инициализации, но поддерживает методы:

• push(item) — добавить элемент в конец очереди;
• pop() — «вытащить» первый элемент из очереди;
• is_empty() — проверят очередь на пустоту.

Примечание

Ваше решение должно содержать только классы и функции.
В решении не должно быть вызовов инициализации требуемых классов.

Пример

Ввод

queue = Queue()
for item in range(10):
    queue.push(item)
while not queue.is_empty():
    print(queue.pop(), end=" ")

Вывод

0 1 2 3 4 5 6 7 8 9 

Ввод

queue = Queue()
for item in ("Hello,", "world!"):
    queue.push(item)
while not queue.is_empty():
    print(queue.pop())

Вывод

Hello,
world!

Решение

С учетом прекрасной реализации списков в python задача элементарная.
Я приведу три решения, первое – минимально необходимое, чтобы пройти тесты, второе с “защитой от дурака” и третье – классическое, такое как если бы в python не было списков и нам пришлось бы писать очередь самостоятельно.

Рассмотрим первый вариант решения.

Решение целиком и полностью построено на списках и не содержит проверки на пустоту списка. Кроме того, оно использует общий экземпляр списка, а это значит, что нельзя одновременно в программе иметь два списка, это вызовет проблему. Но так как по состоянию на 21 декабря 2023 года в тестах Яндекса к этой задаче нет дожных проверок, этот код успешно проходит проверку.

Класс не содержит никакой инициализации, просто объявляет глобальную для всего класса переменную в которую и будут заноситься элементы очереди.
Метод push() просто добавляет элемент в конец нашего списка.
Метод pop() удаляет и возвращает первый элемент нашего списка. Если список окажется пуст, то возникнет ошибка.
Метод is_empty() сравнивает наш список с пустым списком и возвращает результат сравнения.

Второй вариант решения, чуть более продвинутый. Он по-прежнему базируется на встроенных списках, но при этом в нем есть проверка на пустоту списка в методе pop() и в нем можно иметь сколько угодно списков одновременно. Из недостатков, лучше бы оно генерировало ошибку, но так как контролируемую генерацию ошибок мы еще не проходили, остановимся на этом варианте. Как следствие наш список не может содержать элементов None, так как возврат этого значения расценивается как пустой список.

Третий вариант – классический. Такой, которым создавались механизмы очереди двадцать и более лет назад. Еще раньше, вместо объектов использовался тип переменных указатель, но сути решения это не меняло.

Решение основано на элементе Node который является базовым для односвязных списков, очередей, стеков и односвязных колец.

Класс Node представляет из себя объект, содержащий значение текущего элемента очереди и ссылку на следующий объект. В момент создания объекта ссылка на следующий объект определяется как пустое значение (None)

Класс Queue чуть сложнее и выглядит крайне запутанно, если вы не смогли осилить рекурсию. Но даже если не смогли – не отчаивайтесь, возможно самостоятельный разбор этой задачи с бумагой и карандашом продвинет вас в понимании рекурсии.

В момент инициализации он создает две переменные – head (голову) и tail (хвост) списка. Эти переменные нужны для того, чтобы иметь быстрый доступ к началу и концу списка соответственно. В самом начале они принимают “пустое” значение (None).
Метод push() принимает значение и проверяет не пуста ли наша очередь. Если она пуста, то head получает новый элемент Node, а tail указывает на голову списка (tail = head). В противном случае в tail.next помещается новый объект Node(), и сама переменная tail теперь указывает на этот новый объект. Эти операции важно выполнять именно в таком порядке.
Метод pop() проверяет не пуста ли очередь. Если очередь не пуста, то временной переменной присваивается содержимое поля head.item, а head теперь указывает на следующий элемент (head = head.next). Опять же, порядок операций крайне важен.
Метод is_empty() просто проверяет не указывает ли head в пустоту.

# решение наивное. в нем есть ошибки с точки зрения программирования, но оно успешно прозодит тесты Яндекса

class Queue:
    queue = []

    def push(self, item):
        self.queue.append(item)

    def pop(self):
        return self.queue.pop(0)

    def is_empty(self):
        return self.queue == []

# решение c проверкой на допустимость операции. возвращает None если попытаться извлечь элемент когда список пуст

class Queue:
    def __init__(self) -> None:
        self.queue = []

    def push(self, item):
        self.queue.append(item)

    def pop(self):
        item = None
        if not self.is_empty():
            item, *self.queue = self.queue
        return item

    def is_empty(self):
        return self.queue == []

# классическое решение без испольщовнаия встроенных списков.

class Node:
    def __init__(self, item) -> None:
        self.item = item
        self.next = None


class Queue:
    def __init__(self) -> None:
        self.head = self.tail = None

    def push(self, item):
        new_node = Node(item)
        if self.is_empty():
            self.head = new_node
            self.tail = self.head
        else:
            self.tail.next = new_node
            self.tail = new_node

    def pop(self):
        if self.is_empty():
            return None
        temp = self.head.item
        self.head = self.head.next
        return temp

    def is_empty(self):
        return self.head is None