Структура данных — очередь (Python)

Структуры данных

Реализация Python (очередь)

# Полная работающая программа Python Queue в 31 строке кода.

Этап 1 (класс Node)

Реализация очереди достаточно проста. Нам просто нужен класс Node, который хранит значение next и data.

class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None

Этап 2 (Создание головного и конечного узлов)

Для нашей реализации Queue нам нужно создать два эталонных объекта с именами head и tail. Это позволит нам удалитьобъект из головы (представляет начало очереди)и добавитьобъект в хвост (представляет конец очереди).

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

Этап 3 (методы isEmpty и Peek)

Метод isEmpty() очень прост, просто возвращайте значение, если значение заголовка равно нулю;return self.head == None. Если значение заголовка равно нулю, то очередь пуста, в противном случае это не так.

def isEmpty(self):
        return self.head == None

Метод peek() покажет нам 1-е значение в нашей очереди, это достигается с помощью return head.data. Это вызовет исключение, когда заголовок равен нулю. Если вы хотите, вы можете явно проверить это исключение.

def peek(self):
        return self.head.data

Этап 4 (Добавить и удалить узел)

Чтобы добавить узел (в очередь) в конец очереди, сначала необходимо создать узел. Затем, если хвост не равен нулю, пусть следующий указатель хвоста указывает на новый узел, а затем обновляет хвост. Затем мы хотим убедиться, что даже в случае, когда очередь полностью пуста (в этом случае head == null), это значение должно быть значением заголовка.

def enqueue(self, data):
        new_data = Node(data)
        if self.head is None:
           self.head = new_data
           self.tail = self.head
        else:
           self.tail.next = new_data
           self.tail = new_data

Чтобы удалить узел (удалить из очереди) из головы очереди. Первое, что нужно сделать, это получить данные заголовкаdata = self.head.data. Затем мы просто хотим изменить значение заголовка, чтобы оно было следующим значением. Поэтому установите self.head = self.head.next, и это фактически удалит его из очереди. Затем мы говорим, что если значение заголовка равно нулю, убедитесь, что значение хвоста также установлено равным нулю. Затем верните эти данные.

def dequeue(self):
        data = self.head.data
        self.head = self.head.next
        if self.head is None:
           self.tail is None
        return data

Полная реализация

Вот как должен выглядеть ваш код :)

Тестовые случаи

Хорошей практикой является тестирование вашего товара, чтобы увидеть, работает ли он (:

Поздравляем с завершением реализации Python очереди. Итак, это основы реализации Queue. Методы довольно логично вытекают из фактического дизайна и алгоритма, лежащего в его основе. :) !