Научиться реализовывать очередь в Python 3, используя связанный список - PullRequest
Новая
       17

Научиться реализовывать очередь в Python 3, используя связанный список

0 голосов
/ 19 ноября 2018

Я уже давно борюсь с этим.Я реализовал очередь, используя связанный список.Работает нормально, но не знаю почему (?).Я адаптировал метод enqueue из примера Java, но я не могу понять, почему он работает. 

class Node:

def __init__(self, data):
    self.data = data
    self.node= None

class Queue:

def __init__(self):
    self.first = Node(None)
    self.last = Node(None)
    self.n = 0

def enqueue(self, data):
    body = self.last
    self.last = Node(data)  # this is a new node

    if self.is_empty():
        self.first = self.last
    else:
        body.node = self.last # this adds body.node to self.first.node recursively ???? How is body node and self.first.node linked?
    self.n += 1

def dequeue(self):
    result = self.first.data
    self.first = self.first.node
    self.n -= 1
    return result

def is_empty(self):
    return self.n == 0

Проблема заключается в методе enqueue.Я смущен переменной тела.Я провел код через отладчик pycharm и тщательно проследил три переменные узла self.first self.last и body.Как говорится в комментариях, когда body.node = self.last выполняется, новый объект узла присоединяется к self.first.node рекурсивно, так что после трех вызовов enqueue у меня есть объект, который выглядит следующим образом: self.first.node.node.

Каждый узел содержит соответствующие значения данных, и я могу просто прочитать их из очереди с помощью метода dequeue.(Счастливые дни).

Проблема в том, что я не могу понять, почему.Я не вижу, как body программно связан с self.first.

Не могли бы вы объяснить.

1 Ответ

0 голосов
/ 19 ноября 2018

body - это просто ссылка на self.last - это единственное место, где происходит присвоение (body = self.last). Это часто имеет имя tmp или old_last или подобное.

Это необходимо, поскольку self.last больше не ссылается на последний узел в очереди, начиная с self.last = Node(data). Теперь, поскольку body является старым последним , его значение узла было None (это инвариант, который должен быть истинным - проверьте его!). Поскольку мы не хотим, чтобы он был последним больше, мы устанавливаем его для нового узла, который мы создали - на который хорошо ссылается self.last, который мы только что переназначили. Вот почему body.node = self.last прав: последний узел old теперь указывает на последний узел new (который, как мы хотим, указывает на None).

Здесь нет ничего рекурсивного - просто временная переменная, содержащая ссылку на старую последнюю.

Когда очередь пуста, вы попадаете на: 

self.first = self.last

где узел инициализируется впервые (в очереди). Заметьте, это означает, что у вас есть незначительная ошибка , вы теряете первую ссылку в __init__ на первую Node(None), фактически «утечку памяти» в других языках, но это мало что значит в Python.

Настоящая ошибка заключается в том, что если вы дважды dequeue создаете новую очередь - попробуйте. Первый раз установит first на None (что не является Node), а второй сломается, так как None не имеет data члена.

В целом реализация некорректна - я бы ее переделал.

...