我在python中实现了一个队列，是什么使dequeue部分不工作

Question

AM在python中实现队列。我已经完成的代码如下，但有一件事我不能弄清楚的是如何删除队列中的最后一项。我的实现显然是正确的。我在代码

中遗漏了什么?

class Queue:
    class node:
        def __init__(self):
            self.data = None
            self.next = None
    def __init__(self):
        self.cur_node = None
        self.head = None
    def isEmpty(self):
        return self.head==None
    def push(self,data):
        new_node = self.node()
        if self.head == None:
            new_node.data=data
            new_node.next=None
            self.head = new_node
            self.cur_node = None
        else:
            new_node.data = data
            node=self.head
            self.cur_node=node
            new_node.next=self.cur_node
            self.head=new_node
        #set it to head and change current head to next

    def list_print(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next
    def dequeue(self): # A Queue IMPLEMENTS ITS STRUCTURE AS FIFO ( First IN First OUT)
        if self.head == None:
            raise Exception("Queue is empty")            
        else:# Remove the  last item which entered first
            node=self.head
            prevnode=node
            nodetodel=node
            while node:
                if node.next==None:
                    nodetodel=node
                    print(node.data)
                    node=node.next
                else:
                    #print(node.data)
                    node=node.next
                    prevnode=node
            self.cur_node=prevnode
            self.cur_node.next=None
            print(node.data)
            del(node)
lyst = ["Bill", "David", "Susan", "Jane", "Kent", "Brad"]
n=Queue()
for name in lyst:
    n.push(name)
n.dequeue()
#n.list_print()
print("Done")

Answer 1

在我看来，好像你已经实现了你的Queue。head不应该跟踪Queue中最老的值吗?然后要脱离队列，只需执行self.head = self.head.next之类的操作。下面是一个快速实现

class Queue:
    class EmptyQueue(Exception):
        def __str__(self):
            return "Queue is empty, cannot dequeue."    
    class node:
        def __init__(self, data, next):
            self.data = data
            self.next = next
    def __init__(self, seq=None): 
        self.head = None #Oldest item in queue
        self.tail = None #Youngest item in queue
        if seq:
            for item in seq:
                self.enqueue(item)
    def enqueue(self, item):
        new_node = Queue.node(item, None)
        if not self.tail: #queue empty
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
    def dequeue(self):
        if self.head:
            data = self.head.data
            self.head = self.head.next
            return data
        else:
            raise Queue.EmptyQueue
    def list_print(self):
        curr = self.head
        while curr:
            print(curr.data)
            curr = curr.next

Answer 2

我在代码中遗漏了什么

nodetodel未被使用

        #print(node.data)
        node=node.next
        prevnode=node

您应该在更改节点之前设置prevnode，而不是在更改节点之后。

    self.cur_node=prevnode
    self.cur_node.next=None

cur_node作为成员变量是无用的，你不要在任何情况下使用它，局部变量可以很容易地完成这项工作，你已经有一个(prevnode)

    print(node.data)
    del(node)

在执行这两行代码时，已经有了node==None，这是导致程序崩溃的原因。可能您想使用nodetodel。

注:我只是按你的要求指出你的代码中遗漏了什么。我希望它会有所帮助，尽管我个人认为在修复并确保它可以以某种方式工作后，你会考虑@PatrickHaugh的答案并从头开始。

你的queue实现非常低效，因为它必须遍历链表的每个元素。头/尾保持优化的关键是避免需要遍历整个列表才能执行push/pop。

Answer 3

if节点。next==在print语句上下文中dequeue中没有任何部分是错误的。我认为以下更正确(我也简化了):

def dequeue(self): # A Queue IMPLEMENTS ITS STRUCTURE AS FIFO ( First IN First OUT)
    if self.head == None:
        raise Exception("Queue is empty")            
    else:# Remove the  last item which entered first
        node=self.head
        prev = None
        while node:
            if node.next:
                prev = node = node.next
            else:
                self.cur_node = prev
                if prev:
                    prev.next = None
                return node.data

但在实际使用中，您可能只使用内置列表(它可以用作队列)或队列。队列，后者是并发安全的。