Python 链表队列

Question

我试图在python中创建一个链表队列，但是我不知道如何返回列表中的大小和第一个条目……这看起来非常简单。我可以插入和删除，但不能返回大小或第一项。有什么想法吗？？

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


class Queue(object):
  def __init__(self):
    """post: creates an empty FIFO queue"""
    self.length = 0
    self.head = None
    self.tail = None

  def enqueue(self, x):
    """post: adds x at back of queue"""
    newNode = Node(x)
    newNode.next = None
    if self.head == None:
      self.head = newNode
      self.tail = newNode
    else:
      self.tail.next = newNode
      newNode.previous = self.tail
      self.tail = newNode

  def dequeue (self):
    """pre: self.size() > 0
        post: removes and returns the front item"""
    item = self.head.item
    self.head = self.head.next 
    self.length = self.length - 1
    if self.length == 0:
      self.last = None
    return item

  def front(self):
    """pre: self.size() > 0
        post: returns first item in queue"""
    return item[0]

  def size(self):
    """post: returns the number of itemes in queue"""

Answer 1

你在这两个方法中的代码没有任何意义。如何索引到项？它只是节点类的一个字段，而不是数组。为什么不立刻让你想到头部？

令人惊讶的是，剩下的代码看起来还不错。你需要的是：

def front(self):
    return self.head.item

def size(self):
    return self.length

此外，在enqueue（）方法中，不会递增self.length。

事实上，您在这些方面遇到了问题，这应该是一个有用的线索，告诉您您并没有真正理解代码的其余部分。我见过初学者经常陷入这种试错方法的泥潭，在这种方法中，你会一直纠结于某件事情，直到它成功为止，通常是从某个地方得到的一些代码开始。这会导致代码非常脆弱，因为您的理解也很脆弱。这不是编写合理代码的方法。充其量这是建立你的理解的一个起点-在这种情况下，混在一起是正确的做法。通过实验和所有这些来学习。

我建议你仔细阅读你发布的代码，并建立一个合理完整的心理模型来说明它是如何运行的。画图或者其他什么可以帮助你理解这些片段和它们实现的过程。思维模式的深度是编程技能的关键组成部分。

另外，你不需要费尽心思去写这些课程，除了作为练习或其他什么。Python列表已经有一些方法可以将它们用作队列。

Answer 2

Python列表已经完成了您描述的工作。一些例子：

# create a list
l = ['foo', 'bar']

# get the first item
print(l.pop(0))

# add an item
l.append(42)
print(l)

# get the size
print(len(l))

Answer 3

为了有效地报告链接列表的长度，您需要在每次添加元素时将其记录在案，并在每次删除元素时将其递减。你已经在做后者了，但不是前者。

所以，只要在enqueue方法中添加self.length += 1，那么size()就可以简单地成为return self.length

至于队列中的第一个元素，它将始终是head节点中的项。所以front()可以是return self.head.item