1つだけのヘッドポインタを使用してキューのリンクリストを構築する

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がノードにちょうど指し示す変数で、新しいノードを作成し、current.nextに保管する必要がある）、ノート我々 NoneとNodeのコンストラクタをテストするためにis演算子を使用してください（したがって、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のような）は、一定時間内に挿入と削除の両方を行います。