Python链表队列

0 投票

6 回答

13257 浏览

提问于 2025-04-17 23:36

我正在尝试在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"""

数据结构算法链表队列

6 个回答

这是一个定义节点的类，叫做Node。这个类有一个初始化的方法，叫做init。当我们创建一个新的节点时，我们需要给它一些数据，这个数据会被存储在self.data里。self.next是用来指向下一个节点的，刚开始的时候它是None，表示这个节点后面没有其他节点。

接下来是一个定义队列的类，叫做Queue。

def __init__(self):
    self.front = None
    self.rear = None
    self.size = 0

def enQueue(self, data):
    temp = Node(data)
    if self.front == None:
        self.front = self.rear = temp
        self.size += 1 # get track of size
        return
    self.rear.next = temp
    self.rear = temp
    self.size += 1 

def deQueue(self):
    if self.front == None:
        return
    temp = self.front
    self.front = self.front.next
    if self.front == None:
        self.rear = None
    del temp
    self.size -= 1
    
def isEmpty(self): 
    return self.front == None

def getSize(self):
    return self.size

def getFront(self):
    if self.size > 0:
        return self.front.data
    else:
        return

def getRear(self):
    if self.size > 0:
        return self.rear.data
    else:
        return
    
def printQueue(self):
    queue = []
    curr = self.front
    while curr != None:
        queue.append(curr.data)
        curr = curr.next
    print(queue)

回答于 2025-04-17 由 Python大师

分享举报

我首先注意到的是，当你添加新元素时，需要增加列表的长度。size() 方法应该只需要在你做完这件事后返回列表的长度。然后，要访问列表的第一个元素，你似乎在尝试使用列表的语法，但你的列表并不支持这种用法（至少在我看到的代码中是这样）。相反，你应该返回 self.head。

回答于 2025-04-17 由 Python大师

分享举报

你在这两个方法里的代码看起来没什么意义。你是怎么在 item 上进行索引的？它只是 Node 类的一个字段，不是数组。为什么 front() 没有让你立刻想到 head 呢？

令人惊讶的是，你代码的其他部分似乎还不错。你需要的是：

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

def size(self):
    return self.length

另外，你在 enqueue() 方法里没有增加 self.length 的值。

你在这些地方遇到麻烦，说明你对其他代码的理解也不够深入。我见过很多初学者常常陷入试错的方式，随便改改代码直到它能工作，通常是从某个地方抄来的代码。这种做法会导致代码非常脆弱，因为你的理解也很脆弱。这不是写出合理代码的方式。顶多这只是建立你理解的起点——在这种情况下，随便改改确实是对的。通过实验来学习就是这样。

我建议你仔细阅读你发布的代码，建立一个比较完整的心理模型，理解它是怎么运作的。可以画图或者用其他方法帮助你理解各个部分和它们实现的过程。你心理模型的深度是编程技能的一个关键因素。

另外，除了作为练习，你其实不需要费这么大劲去写这些类。Python 的列表已经有可以用作队列的方法了。

回答于 2025-04-17 由 Python大师

分享举报

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))

回答于 2025-04-17 由 Python大师

分享举报

为了高效地报告链表的长度，你需要在每次添加一个元素时把长度加1，而在每次删除一个元素时把长度减1。你已经在做删除时的减法了，但添加时的加法还没有。

所以，只需要在你的 enqueue 方法里加上 self.length += 1，这样 size() 方法就可以简单地写成 return self.length。

至于队列中的第一个元素，它总是位于 head 节点里。所以 front() 方法可以写成 return self.head.item。

回答于 2025-04-17 由 Python大师

分享举报

Python链表队列

6 个回答

撰写回答