只使用一個頭指針構造一個隊列鏈表

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）將在固定時間內進行插入和刪除操作。