只使用一个头指针构造一个队列链表

Question

我想用一个头指针（无尾）构造一个队列链表。 但我似乎无法入列列表的末尾。

示例：此刻代码将：c -> b -> a，但是我想将其反转a -> b -> c。

class Node: 
    '''A node for a linked list.''' 

    def __init__(self, initdata): 
     self.data = initdata 
     self.next = None 

class Queue(object): 

    def __init__(self): 
     self.head = None 

    def enqueue(self, item): 
     """Add an item onto the tail of the queue.""" 
     if self.head == None: 
      temp = Node(item) 
      temp.next = self.head 
      self.head = temp 
     else: 
      current = self.head 
      while current != None: 
       current = current.next 
      if current == None: 
       temp = Node(item) 
       temp.next = current 
       current = temp 

    def dequeue(self): 
     if self.head == None: 
      raise IndexError("Can't dequeue from empty queue.") 
     else: 
      current_first = self.head 
      current = self.head.next 
      return current_first.data 

Answer 1

这应做到：

class Node: 
    '''A node for a linked list.''' 
    def __init__(self, initdata): 
     self.data = initdata 
     self.next = None 

class Queue(object): 
    def __init__(self): 
     self.head = None 

    def enqueue(self, item): 
     """Add an item onto the tail of the queue.""" 
     if self.head is None: 
      self.head = Node(item) 
     else: 
      current = self.head 
      while current.next is not None: 
       current = current.next 
      current.next = Node(item) 

    def dequeue(self): 
     if self.head is None: 
      raise IndexError("Can't dequeue from empty queue.") 
     else: 
      first = self.head 
      self.head = self.head.next 
      return first.data 

除了一些逻辑修正（我们需要创建一个新的节点，并将其存储在current.next，current只是一个变量指向一个节点），注意，我们使用is运算符来测试None和Node构造函数来设置数据（所以我们可以创建并分配新节点，而不需要使用temp var）。

例如：

q = Queue() 
q.enqueue('a') 
q.enqueue('b') 
q.enqueue('c') 

print(q.dequeue()) 
print(q.dequeue()) 
print(q.dequeue()) 

输出：

a 
b 
c 

顺便说一句，请注意，这样的结构需要O(N)插入时间和O(1)缺失（弹出）的时间。双端队列（如标准collections.deque）将在固定时间内进行插入和删除操作。