python - 打印链表队列中的元素

Question

我在 python 中有以下代码。我的问题是如何打印链接队列中的每个元素？我知道我必须制作一个 __repr__ 或 __str__ 函数，但我不确定如何实现它。谢谢。

class LinkedQueue :
    class _Node :
        def __init__(self, element, next):
            self._element = element
            self._next = next


        def get_elements():
            return self._element

        def set_elements(num):
            self._element = num    

    def __init__(self) :
        self._head = None
        self._tail = None
        self._size = 0

    def __len__(self) :
        return self._size

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

    def first(self) :
        if self.is_empty() :
            raise Empty('Queue is empty')
        return self._head._element

    def dequeue(self) :
        if self.is_empty():
            raise Empty('Queue is empty')
        answer = self._head._element
        self._head = self._head._next
        self._size -= 1
        if self.is_empty() :
            self._tail = None
        return answer

    def enqueue(self, e) :
        newest = self._Node(e,None)
        if self.is_empty() :
            self._head = newest
        else :
            self._tail._next = newest
        self._tail = newest
        self._size += 1

class Empty(Exception) :
    pass    

Answer 1

这取决于您希望 repr 看起来像什么，但这是一种方法。我们给 _Node 类一个简单的 __repr__ ，它只返回元素的 repr，并为 LinkedQueue 实例构建 repr，我们遍历链表，将每个节点的repr存储到一个列表中。然后我们可以在该列表上调用 .join 来生成 LinkedQueue 的 repr。

class Empty(Exception): 
    pass

class LinkedQueue: 
    class _Node:
        def __init__(self, element, _next=None):
            self._element = element
            self._next = _next

        def __repr__(self):
            return repr(self._element)

    def __init__(self): 
        self._head = None
        self._tail = None
        self._size = 0

    def __len__(self): 
        return self._size

    def __repr__(self):
        lst = []
        head = self._head
        while head is not None:
            lst.append(repr(head))
            head = head._next
        return 'Queue({})'.format(", ".join(lst))

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

    def first(self): 
        if self.is_empty(): 
            raise Empty('Queue is empty')
        return self._head._element

    def dequeue(self): 
        if self.is_empty():
            raise Empty('Queue is empty')
        answer = self._head._element
        self._head = self._head._next
        self._size -= 1
        if self.is_empty(): 
            self._tail = None
        return answer

    def enqueue(self, e): 
        newest = self._Node(e)
        if self.is_empty(): 
            self._head = newest
        else: 
            self._tail._next = newest
        self._tail = newest
        self._size += 1

# test

q = LinkedQueue()
for u in 'abcd':
    q.enqueue(u)
    print(len(q))

print(q)

while not q.is_empty():
    print(q.first(), q.dequeue())

输出

1
2
3
4
Queue('a', 'b', 'c', 'd')
a a
b b
c c
d d

---

我摆脱了 Node 中的 getter 和 setter 方法，因为您不使用它们，而且我们通常不会像在 Python 中那样编写 getter 和 setter。查看Descriptor HowTo Guide在文档中。

FWIW，我会让 Node 成为一个单独的类(或者完全摆脱它)，而不是将它嵌套在 LinkedQueue 中。我想嵌套它并没有坏处，但嵌套类定义在 Python 中并不经常使用。

顺便说一句，collections.deque是一个非常高效的双端队列。对于简单的队列和堆栈，它通常比 list 更快。但我想这个 LinkedQueue 类是用于在 Python 中实现链表的练习，因此 collections.deque 目前与您无关。 ;)